Algorithm Design and Complexity, III/1, 2C, 0S, 1 L, 0P, C, 4

back 
Course description 
This course is an i ntroduction to the design, behavior, and analysis of computer algorithms. Searching, sorting, and combinatorial algorithms are emphasized. In the first part, a number of standard algorithm design paradigms are presented and example applications of these examined. In the second part of the course, some theoretical issues in algorithm design are examined. The concepts of computability and computational tractability are introduced.

Prerequisite(s) & Corequisite(s)

Prerequisites: "Data Structures and Algorithms". Knowledge and experience of programming in a highlevel imperative language (Java, C++, or C).
The "Formal Languages & Automata" course should carry on and supplement this course with other, specific topics. 
Textbook(s) and web materials 
• A.V.Aho, J.D.Ullman, Foundations of Computer Science (Principles of Computer Science Series), W. H. Freeman & Co, 1995.
• D.E.Knuth, The Art of Computer Programming , v.13, 2/e, AddisonWesley, 1998. (there is also an edition in Romanian)
• C.Giumale, L.Negreanu, S.Călinoiu  Proiectarea si analiza algoritmilor, Editura All Educational, Bucuresti, 1996
• Michael T. Goodrich, Roberto Tamassia, Algorithm Design: Foundations, Analysis, and Internet Examples, John Wiley & Sons, 2001. 
Course objectives 
• To introduce the student to basic algorithmic analysis techniques. • To familiarize the student with fundamental strategies in algorithmic design. • To teach the student implementation techniques for complex data structures such as graphs, trees, and networks, to familiarize the student with performance issues related to these structures, and to provide the student with a broad range of algorithms for manipulating them • To teach the student to handle asymptotic complexity bounds of algorithms. • To prepare the student for additional study in computer science 
Topics covered

Algorithm Analysis. How to characterize an algorithm's behavior and how to compare two algorithms? Quantification of resources used by algorithms. Asymptotic upper, lower, and tight bounds on time and space complexity of algorithms. (2h)
Case Studies in Algorithm Analysis. Abstract Data Type Definition. Complexity analysis of some wellknown implementation solutions for basic ADTs (stack, queue, vector, list, sequence, set, tree, priority queue, heap, dictionary, hash table). (4h)
Analysis of Searching Algorithms. Ordered Dictionaries. Binary Search Trees. Balanced Binary Search Trees (RedBlack trees, BTrees, 23 trees) (3h)
Analysis of Sorting and Selection Algorithms. MergeSort. QuickSort. A Lower Bound on ComparisonBased Sorting. Comparison of Sorting Algorithms. Selection. (4h)
Fundamental Techniques. The Greedy Method. DivideandConquer. Dynamic Programming. (4h)
Graphs. The Graph Abstract Data Type. Data Structures for Graphs. Graph Traversal. Directed Graphs. (4h)
Weighted Graphs. SingleSource Shortest Paths. AllPairs Shortest Paths. Minimum Spanning Trees. Dijkstra's Algorithm. (4h)
Networks. Flows and Cuts. Maximum Flow. Maximum Bipartite Matching. MinimumCost Flow. (2h)
Foundations of algorithms. Models of algorithmic process and their universality: ChurchTuring hypothesis. Polynomial versus NonPolynomial time complexity. (2h)
NPcompleteness. Important NPComplete problems. Approximation algorithms. Backtracking and BranchandBound (3h) 
Laboratory 
Laboratory consists of discussion, problem solving, and presentation of homework solutions. Prereading of the lecture notes and class attendance is essential and students are expected to be prepared and to actively participate in class activities. There are about 7 assignments, due two weeks after the student get them. Assignments should be prepared for the next class period. Some may be collected for grading; others will be reviewed in class.

Grading 
Grading will be as follows:
60% Final exam (individual quiz + a set of small problems)
40% Homework assignments, unannounced quizzes and personal contribution to laboratory classes. 
Professional significance 
The topic of algorithmic analysis is central to computer science. Its goal is to explore and examine a range of algorithms that can be used to solve practical problems. As we know, each algorithm possesses strengths and weaknesses. Moreover, the performance or any particular algorithm typically varies according to the size and nature of the input data. Students need a thorough understanding of the tools of analysis in order to select the right algorithm for the job. This is exactly what this course intends to offer.

