Algorithm analysis provides the theoretical background for buildina correct, efficient alaorithms to solve real life problems.
Students will learn the art of problem solving through studying fundamental alaorithm design techniques.
Emphasis is on recursion, search, sorting, and graph and tree algorithms, implementation and on application of various algorithmic strategies

Key Topics
Topics to be covered include Asymptotic notation; Sums and Recurrences: Divide andConquer; Dynamic Programming: Greedy Algorithms; Graph Algorithms; Advanced DataStructures; Machine Learning algorithms and NP Completeness for decision problems.

Learning Outcomes:
Students who have completed this course should be able to
1. Use discrete mathematics in analysis of algorithms
2. Understand different algorithmic design strategies
3. Analyze the efficiency of algorithms using time and space complexity theory
4. Apply design principles and concepts to algorithm design

Assessment methods of all of the above: assignments, exams, term project

Required Textbook
Sara Baase, Allen Van Gelde, "Computer Algorithms", 3rd Ed.,Addison-Wesley,2000, ISBN-0-201-61244-5

Recommended book T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, "Introduction to Algorithms,"3rd Ed., MIT Press, 2009, ISBN-13: 9780262033848.

Courseware
The lecture notes will be available in traditional digital-file formats (*.doc,*.ppt, and *.pdf) on the blackboard site related

Evaluation and Grading Policy
There will be two exams. If any grading criteria event will be missed it will be the responsibility of the student to arrange a mutually agreeable schedule forcompletion of work.

An assignment will be considered late, if you fail to hand in the assignment by the specified ime and date, and you will be charged 10 pts.
Charge will be waived in case of circumstances are beyond your control.

You may resubmit your corrected assignment however you will be charged 5 pts per each submission. Charge will be waived in case of circumstances are beyond your control.

The grade is made up of your performance on your home works, project paper, midterm, inal exams and participation.

Participation will be based on the percentage of in-class polling questions answered. Correctness of in-class polling responses will not be taken into account for participation grades.

Approximate weightings are as following:

Assignments	Percentage
Six Written Homework Assignments	48%
In Class Participation	4%
Midterm Exam	24%
Final Exam (or Project Paper)	24%

Letter Grade:

A	A-	B+	B	B-	C+	C	C-	D	F
94  G	90  G< 94	87  G< 90	83  G< 87	80  G< 83	77  G<80	73  G<77	70  G<73	60<G<70	G<70

There will be no make-up exam for the final exam. If a student cannot take the final exam on the designated day, she/he will receive an incomplete grade.

SESSION	TOPIC	Text book READING
1 (01/28)	Preliminaries (Chapters 1-2): What is an algorithm? Principles of algorithm analysis and design. Classification of functions by their asymptotic growth rate. Biq-O and similar otations. Abstract Data Type (ADT) specification and design techniques.	Ch. 1, 2
2 (02/04)	Elementary ATDs: lists, trees, stacks, queues, and dynamic sets. Recurrence equations and their solution. Applications of recurrences. Induction proofs and examples. Principles of proving correctness of procedures. Review of series and sets, some probability.	Ch. 2, 3
3 (02/11)	Sorting Algorithms (Heapsort, quicksort, merge sort, and radix sort). Proof that sorting (by comparisons) takes O(n log(n)) time. Medians and order statistics.	Ch. 4
4 (02/18)	Divide and conquer techniques for mergesort and quicksort.	Ch. 4, 5
5 (02/25)	Dynamic Sets: Amortized time analysis; Hashing	Ch. 6
6 (03/04)	Graph algorithms: Spanning trees or forests; Shortest paths and Maximum flow. Mid-term Exam Preparation	Ch. 7, 9
7 (03/11)	MID-TERM EXAM	Ch. 1-7
8 (03/18)	Graph optimization problems, greedy ano Minimum Spanning Tree algorithms: Huffmar codes	Ch. 8
9 (03/25)	Dynamic programming; Examples and principles;	Ch. 10
10 (04/01)	String matching: Rabin-Karp and Knuth-Morris-Pratt algorithms.	Ch. 11
11 (04/08)	NP-complete problems; Virtual Reality	Ch. 13
12 (04/15)	Machine Learning;
13 (04/22)	Deep Machine Learning: Miscellaneous topics	Slide Presentation
14 (04/29)	Projects Presentations: Final Exam Preparation
15 (05/06)	FINAL EXAM or Project Paper	Ch. 8-13

Homework-1

Due – 02/02

 
All work must be your own. Any collaboration, etc., will earn you a quick “0” and a notification of the CS Department. 

No extensions or late submissions for anything other than major emergency. 

(1)  [10 pts.] 

Give a formula for SUM{i} [i changes from i=a to i=n], where a is an integer between 1 and n.

(2)  [10 pts.] 

Suppose Algorithm-1 does f(n) = n**2 + 4n steps in the worst case, and Algorithm-2 does g(n) = 29n + 3 steps in the worst case, for inputs of size n. For what input sizes is Algorithm-1 faster than Algorithm-2 (in the worst case)?

(3)  [10 pts.] 

Prove or disprove: SUM{i**2} [where i changes from i=1 to i=n]  ϵ  theta(n**2).

(4)  [10 pts.] 

Write out the algorithm (pseudocode) to find K in the ordered array by the method that compares K to every fourth entry until K itself or an entry larger than K is found, and then, in the latter case, searches for K among the preceding three. How many comparisons does your algorithm do in the worst case?

(5)  [20 pts.] Design and implement (meaning write code and execute the code turning in test cases and source code) for the following two algorithms to raise an integer to an integer power assume in both cases that n, the exponent, is a power of 2:

Again, in case you don’t have any programming language at hand you can use pseudocode to solve the problem.

Algorithm 1

X**N = X* X**(N-1)
X**0 = 1

Algorithm 2

n = 2**m

X**n = ((X**2)**2)**2…, etc. [NOTE: the symbol of power (**) is used m times here, i.e., X**8 =  ((X**2)**2)**2, because 8 = 2**3].

Which algorithm is more efficient with respect to the number of multiplications?

(6)  [20 pts.] Answer questions (a) and (b) below:

(a)  How many times exactly is the code block below executed?

 

For (i = 1, n)

{

For (j = 1, i)

{

For (k = 1, j)

{

code block

}

}

}

 
Hint: You have to start with n=1, then make assumption what you make expect for any given n = N, and check if the formula you found works for n =N+1.
This is what we call prove by induction.

(b) What is the theta value of this code segment?