Analysis and Design of Algorithms

Objectives

The objectives of this course are:

  1. Demonstrating the importance of the analysis and design of algorithms.
  2. Teaching mathematical tools used in the analysis and evaluation of algorithms.
  3. Teaching important classes of algorithms. These are mainly the brute-force, greedy, divide-and-conquer, backtracking, branch-and-bound, heuristics, and numerical approximation algorithms.
  4. Familiarizing students with common concrete examples of algorithms taken from different applications such as searching, sorting, tree traversal, finding the shortest paths, scheduling, optimization, graph traversal, graph exploration (backtracking and branch-and-bound), and numerical approximation.
  5. Explain the distributed paradigm, consensus, and leader election.
  6. Distinguish between logical and physical clocks, and describe the relative ordering of events in a distributed algorithm.
Back to Top

Syllabus

The main topics covered in this course are:

  1. An introduction to algorithms: basic definitions, approximate algorithms, and heuristics. Simple examples.
  2. Efficiency of algorithms; average and worst-case analyses; elementary operations; examples.
  3. Asymptotic notation; Big O, Little o, Omega and Theta notations.
  4. Analysis of control structures and simple algorithms.
  5. Deducing recurrence relations that describe the time complexity of recursively defined algorithms, and solving them.
  6. Some data structures: graphs, trees, associative tables, heaps, and binomial heaps.
  7. Brute-force algorithms.
  8. Greedy Algorithms.
  9. Divide-and Conquer algorithms.
  10. Backtracking and branch-and-bound algorithms.
  11. Numerical approximation algorithms.
  12. Definition and characteristics of distributed systems.
  13. Consensus and leader election in distributed systems.
  14. The logical ordering of events in distributed systems.
Back to Top

Textbook and References

Textbooks:

  1. Fundamentals of Algorithmics, Gilles Brassard and Paul Brately, Prentice-Hall International, 1996.
  2. Distributed Operating Systems , Tanenbaum Andrew, Prentice-Hall, 1995.

References:

  1. Designing and Building Parallel Programs, Ian Foster, Addison-Wesley, 1995.
Back to Top

Grading Policy

There are two tests, one final exam, and about 10 homeworks consisting of approximately 30 to 40 problems and exercises. Students are to submit their homeworks to their instructor using Email. A randomly selected subset of the homeworks will be graded. Students are encouraged to cooperate, but the homeworks are to be prepared and submitted individualy. The tests and final exams strongly depend on the homeworks.

The evaluation components defined above will carry the following weights:

  1. Test 1: 20%
  2. Test 2: 20%
  3. Homeworks: 10%
  4. Final Exam: 50%
Back to Top

Related Information

The following information was Extracted from ACM Computing Curricula 2001 on the Internet

Algorithms and Complexity (AL)

Algorithms are fundamental to computer science and software engineering. The real-world performance of any software system depends on only two things: (1) the algorithms chosen and (2) the suitability and efficiency of the various layers of implementation. Good algorithm design is therefore crucial for the performance of all software systems. Moreover, the study of algorithms provides insight into the intrinsic nature of the problem as well as possible solution techniques independent of programming language, programming paradigm, computer hardware, or any other implementation aspect.

An important part of computing is the ability to select algorithms appropriate to particular purposes and to apply them, recognizing the possibility that no suitable algorithm may exist. This facility relies on understanding the range of algorithms that address an important set of well-defined problems, recognizing their strengths and weaknesses, and their suitability in particular contexts. Efficiency is a pervasive theme throughout this area.

AL1. Basic algorithmic analysis [core]

Minimum core coverage time: 4 hours

Topics:

  1. Asymptotic analysis of upper and average complexity bounds
  2. Identifying differences among best, average, and worst case behaviors
  3. Big O, little o, omega, and theta notation
  4. Standard complexity classes
  5. Empirical measurements of performance
  6. Time and space tradeoffs in algorithms
  7. Using recurrence relations to analyze recursive algorithms

Learning objectives:

  1. Explain the use of big O, omega, and theta notation to describe the amount of work done by an algorithm.
  2. Use big O, omega, and theta notation to give asymptotic upper, lower, and tight bounds on time and space complexity of algorithms.
  3. Determine the time and space complexity of simple algorithms.
  4. Deduce recurrence relations that describe the time complexity of recursively defined algorithms.
  5. Solve elementary recurrence relations.

AL2. Algorithmic strategies [core]

Minimum core coverage time: 6 hours

Topics:

  1. Brute-force algorithms
  2. Greedy algorithms
  3. Divide-and-conquer
  4. Backtracking
  5. Branch-and-bound
  6. Heuristics
  7. Pattern matching and string/text algorithms
  8. Numerical approximation algorithms

Learning objectives:

  1. Describe the shortcoming of brute-force algorithms.
  2. For each of several kinds of algorithm (brute force, greedy, divide-and-conquer, backtracking, branch-and-bound, and heuristic), identify an example of everyday human behavior that exemplifies the basic concept.
  3. Implement a greedy algorithm to solve an appropriate problem.
  4. Implement a divide-and-conquer algorithm to solve an appropriate problem.
  5. Use backtracking to solve a problem such as navigating a maze.
  6. Describe various heuristic problem-solving methods.
  7. Use pattern matching to analyze substrings.
  8. Use numerical approximation to solve mathematical problems, such as finding the roots of a polynomial.

AL3. Fundamental computing algorithms [core]

Minimum core coverage time: 12 hours

Topics:

  1. Simple numerical algorithms
  2. Sequential and binary search algorithms
  3. Quadratic sorting algorithms (selection, insertion)
  4. O(N log N) sorting algorithms (Quicksort, heapsort, mergesort)
  5. Hash tables, including collision-avoidance strategies
  6. Binary search trees
  7. Representations of graphs (adjacency list, adjacency matrix)
  8. Depth- and breadth-first traversals
  9. Shortest-path algorithms (Dijkstra's and Floyd's algorithms)
  10. Transitive closure (Floyd's algorithm)
  11. Minimum spanning tree (Prim's and Kruskal's algorithms)
  12. Topological sort

Learning objectives:

  1. Implement the most common quadratic and O(NlogN) sorting algorithms.
  2. Design and implement an appropriate hashing function for an application.
  3. Design and implement a collision-resolution algorithm for a hash table.
  4. Discuss the computational efficiency of the principal algorithms for sorting, searching, and hashing.
  5. Discuss factors other than computational efficiency that influence the choice of algorithms, such as programming time, maintainability, and the use of application-specific patterns in the input data.
  6. Solve problems using the fundamental graph algorithms, including depth-first and breadth-first search, single-source and all-pairs shortest paths, transitive closure, topological sort, and at least one minimum spanning tree algorithm.
  7. Demonstrate the following capabilities: to evaluate algorithms, to select from a range of possible options, to provide justification for that selection, and to implement the algorithm in programming context.

AL4. Distributed algorithms [core]

Minimum core coverage time: 3 hours

Topics:

  1. Consensus and election
  2. Termination detection
  3. Fault tolerance
  4. Stabilization

Learning objectives:

  1. Explain the distributed paradigm.
  2. Explain one simple distributed algorithm.
  3. Determine when to use consensus or election algorithms.
  4. Distinguish between logical and physical clocks.
  5. Describe the relative ordering of events in a distributed algorithm.

AL5. Basic computability [core]

Minimum core coverage time: 6 hours

Topics:

  1. Finite-state machines
  2. Context-free grammars
  3. Tractable and intractable problems
  4. Uncomputable functions
  5. The halting problem
  6. Implications of uncomputability

Learning objectives:

  1. Discuss the concept of finite state machines.
  2. Explain context-free grammars.
  3. Design a deterministic finite-state machine to accept a specified language.
  4. Explain how some problems have no algorithmic solution.
  5. Provide examples that illustrate the concept of uncomputability.

AL6. The complexity classes P and NP [elective]

Topics:

  1. Definition of the classes P and NP
  2. NP-completeness (Cook's theorem)
  3. Standard NP-complete problems
  4. Reduction techniques

Learning objectives:

  1. Define the classes P and NP.
  2. Expsignificance of NP-completeness.
  3. Prove that a problem is NP-complete by reducing a classic known NP-complete problem to it.

AL7. Automata theory [elective]

Topics:

  1. Deterministic finite automata (DFAs)
  2. Nondeterministic finite automata (NFAs)
  3. Equivalence of DFAs and NFAs
  4. Regular expressions
  5. The pumping lemma for regular expressions
  6. Push-down automata (PDAs)
  7. Relationship of PDAs and context-free grammars
  8. Properties of context-free grammars
  9. Turing machines
  10. Nondeterministic Turing machines
  11. Sets and languages
  12. Chomsky hierarchy
  13. The Church-Turing thesis

Learning objectives:

  1. Determine a language's location in the Chomsky hierarchy (regular sets, context-free, context-sensitive, and recursively enumerable languages).
  2. Prove that a language is in a specified class and that it is not in the next lower class.
  3. Convert among equivalently powerful notations for a language, including among DFAs, NFAs, and regular expressions, and between PDAs and CFGs.
  4. Explain at least one algorithm for both top-down and bottom-up parsing.
  5. Explain the Church-Turing thesis and its significance.

AL8. Advanced algorithmic analysis [elective]

Topics:

  1. Amortized analysis
  2. Online and offline algorithms
  3. Randomized algorithms
  4. Dynamic programming
  5. Combinatorial optimization

Learning objectives:

  1. Use the potential method to provide an amortized analysis of previously unseen data structure, given the potential function.
  2. Explain why competitive analysis is an appropriate measure for online algorithms.
  3. Explain the use of randomization in the design of an algorithm for a problem where a deterministic algorithm is unknown or much more difficult.
  4. Design and implement a dynamic programming solution to a problem.

AL9. Cryptographic algorithms [elective]

Topics:

  1. Historical overview of cryptography
  2. Private-key cryptography and the key-exchange problem
  3. Public-key cryptography
  4. Digital signatures
  5. Security protocols
  6. Applications (zero-knowledge proofs, authentication, and so on)

Learning objectives:

  1. Describe efficient basic number-theoretic algorithms, including greatest common divisor, multiplicative inverse mod n, and raising to powers mod n.
  2. Describe at least one public-key cryptosystem, including a necessary complexity-theoretic assumption for its security.
  3. Create simple extensions of cryptographic protocols, using known protocols and cryptographic primitives.

AL10. Geometric algorithms [elective]

Topics:

  1. Line segments: properties, intersections
  2. Convex hull finding algorithms

Learning objectives:

  1. Describe and give time analysis of at least two algorithms for finding a convex hull.
  2. Justify the Omega(N log N) lower bound on finding the convex hull.
  3. Describe at least one additional efficient computational geometry algorithm, such as finding the closest pair of points, convex layers, or maximal layers.

AL11. Parallel algorithms [elective]

Topics:

  1. PRAM model
  2. Exclusive versus concurrent reads and writes
  3. Pointer jumping
  4. Brent's theorem and work efficiency

Learning objectives:

  1. Describe implementation of linked lists on a PRAM.
  2. Use parallel-prefix operation to perform simple computations efficiently in parallel.
  3. Explain Brent's theorem and its relevance.
December 15, 2001

Stanford University:

161. Design and Analysis of Algorithms-Efficient algorithms for sorting, searching, and selection.Algorithm analysis: worst and average case analysis. Recurrences and asymptotics. Data structures: balanced trees, heaps, etc. Algorithm design techniques: divide-and-conquer, dynamic programming, greedy algorithms, amortized analysis. Algorithms for fundamental graph problems, e.g., depth-first search, connected components, topological sort, shortest paths. Possible topics: network flow, string searching, parallel computation. Prerequisite: 103 or 109, Statistics 116.

*4 units, Aut (Plotkin), Win (Guibas)

Back to Top

Instructor & Office Hours

Fall 2002/2003

Ismail Ababneh, Acting Dean of the IT College
Dean's Office, Information Technology College

Office Hours: 12-1 Sunday; 9-10 Tuesday and Thursday; 8:15 to 9:15 Monday

Office phone
(962) 6 4871101 ext 3351

Electronic mail address
cs340@alalbayt.aabu.edu.jo

Back to Top
Last revised: 29-10-2002.