CST 370 Week 1

This was our first week in CST 370 - Design and Analysis of Algorithms.

What is an algorithm?

Our textbook, Introduction to the design and analysis of algorithms, defines an algorithm as a sequence of unambigous instructions for solving a problem. It also gives a list of important points for algorithm design (p. 29):

  •  The nonambiguity requirement for each step of an algorithm cannot be compromised.
  •  The range of inputs for which an algorithm works has to be specified carefully.
  •  The same algorithm can be represented in several different ways.
  •  There may exist several algorithms for solving the same problem.
  •  Algorithms for the same problem can be based on very different ideas and
    can solve the problem with dramatically different speeds.

 

Another important idea is that algorithms are system agnostic. They can be implemented in any programming language, or even done manually. The textbook presents algorithms using psuedocode.

Algorithm Examples 

Euclid's Algorithm

The first algorithm the textbook discusses is Euclid's algorithm. This, along with the first few algorithms, are used to try and find the greatest common divisor of two numbers.

 

 Consecutive Integer Checking Algorithm

 

Middle-School Procedure 

Types of Problems

The textbook covers a handful of important types of problems in algorithm design.

  • The sorting problem is to rearrange the items of a given list in a certain order.
  • The searching problem deals with finding a given value in a given set.
  • String problems deal with analyzing and manipulating strings, sequences of alphabetic characters.
  • Graph problems deal with graphs, collections of connected points. Types of graphs include directed and undirected graphs, weighted and unweighted graphs, and trees.
  • Combinatorial problems ask to find a combinatorial object, such as a permutation, a combination, or a subset that satisfies certain constraints.
  • Geometric problems deal with geometric objects such as points, lines, and polygons.
  • Numerical problems deal with numbers, equations, functions, and other mathematical operations.

Orders of Growth

In analysizing the efficiency of algorithms, we often use an algoritm's order of growth to show how long it takes to complete for a certain input size.

 

Algorithm efficiency is often measured using best-case and worst-case scenarios.

  • An algorithm's best-case scenario is one where the algorithm is completed as quickly as possible. An example of this is finding the correct value in the first element of an array.
  • An algorithm's worst-case scenario is one where the algorithm is completed as slowly as possible. An example of this is finding the correct value in the last element of an array, or not at all.

Comments

Post a Comment

Popular posts from this blog

Week 11

CST-338 Week 3  This week was the third week of CST-338. In this week we continued to learn more design and Java concepts. Black Box & White Box Testing This week we learned about two methodologies used for testing programs, black box and white box testing. Black box tests only focuses on the input, output, and functionality of a program, and not the internal code, logic, or structure of a program. One of the advantages of black box tests is that they are simple and easy to run. White box tests focus on the code, logic, and structure of a program. One of the advantages of white box tests is that can find logical errors, security vulnerabilities, or inefficiencies in code. Coupling & Cohesion This week we learned about coupling and cohesion in objects and methods. Coupling refers to how much different classes rely on each other. If two classes have tight coupling then they are more dependent, and changes in one are more likely to affect the other. If two classes have loose c...
Read more

Week 12

CST 338 - Week 4 This week was the fourth week is CST 338, also known as Software Engineering. In this week we began to learn about android development. Project 1 Review This week we finished a large project in CST 338. We have been asked to work with one or more classmates, and answer some questions about the project. With whom did you work? I worked with Nasser. What was your strategy for solving the assignments? My strategy was to read all of the method descriptions before I wrote any code. As I read them I created method stubs, and detailed TODO comments for each method. Afterwards, I started writing the methods from top to bottom in the assignment prompt. If a method called another method that I had not written yet, I would go ahead and write that method first so I better understood how they interacted. What was their strategy for solving the assignments? Their strategy was to follow the instructions closely as is, by following the UML diagrams and prompt as closely as possible. ...
Read more

Week 19

Image
 CST-363: Week 3 This is the third week of CST-363, also known as Intro. to Databases. Questions What is an SQL view.  How is it similar to a table? In what ways is it different? An SQL View stores a SELECT statement for later use, allowing the statement to be easily accessed in the future. A View functions similarly to a table, because SELECT statements return tables. However, the values that a View shows aren't being stored in the View, but the actual tables. This means that when one of those tables is updated, the View has to be as well. This also means that one needs to be very careful with updating or deleting rows using the View. Take a minute to think about how SQL compares to other programming languages like Java. What features are similar, and which are present in one language but not the other? The first and most clear difference is the syntax. SQL syntax is very different from that of Java and other programming languages. I think this makes basic SQL commands easy t...
Read more