       ## Syllabus ( CSE 321 )

 Basic information Course title: Introduction To Algorithm Design Course code: CSE 321 Lecturer: Assoc. Prof. Dr. Didem GÖZÜPEK ECTS credits: 6 GTU credits: 3 (3+0+0) Year, Semester: 3, Fall Level of course: First Cycle (Undergraduate) Type of course: Compulsory Language of instruction: English Mode of delivery: Face to face Pre- and co-requisites: CSE 211 & CSE 222 Professional practice: No Purpose of the course: This course aims to introduce basic algorithms and algorithm design techniques which can be used in designing solutions to real life problems, analyze the solutions based on several criteria such as running-time, memory usage and energy consumption.
 Learning outcomes Upon successful completion of this course, students will be able to:

1. Design algorithmic solutions using algorithm design techniques

### Contribution to Program Outcomes

1. Obtain basic knowledge of Computer Engineering
2. Design and develop hardware and/or software-based systems, components or processes in order to solve the defined problems.

### Type of Assessment

1. Homework assignment
2. Analyze algorithms with respect to various performance criteria such as memory use and running time

### Contribution to Program Outcomes

1. Obtain basic knowledge of Computer Engineering
2. Define and analyze engineering problems by using the mathematics, scientific and engineering knowledge,

### Type of Assessment

1. Written exam
2. Homework assignment
3. Distinguish between various algorithm design techniques

### Contribution to Program Outcomes

1. Obtain basic knowledge of Computer Engineering

### Type of Assessment

1. Written exam
4. Choose the best algorithm with respect to various performance criteria

### Contribution to Program Outcomes

1. Obtain basic knowledge of Computer Engineering

### Type of Assessment

1. Written exam
 Contents Week 1: Background Information: Discrete mathematics; Data structures. Introduction to Algorithms: What is an algorithm; Various problems. Analysis of Algorithms: Complexity of algorithms; Asymptotic notations. Week 2: Recursive Functions and Their Solutions: Substitution method; Characteristic equation method, Master’s theorem. Week 3: Brute Force Method: Sorting Algorithms; Searching algorithms; String matching problem; Closest pair problem; Convex-Hull problem; Exhaustive search. Week 4: Divide-and-Conquer: Sorting Algorithms; Searching algorithms; Closest pair problem; Convex-Hull problem. Week 5: Decrease-and-Conquer: Sorting algorithms; Graph algorithms, Depth-First Search, Breadth-First Search, and topological sorting; Algorithms for generating combinatorial objects; Fake coin problem; Selection problem. Week 6: Transform-and-Conquer: Presorting; Gaussian elimination; Balanced searched trees; Heaps and heapsort; Horner’s rule and binary exponentiation; Problem reduction. Week 7: Midterm exam I Week 8: Dynamic Programming: Knapsack problem; All pairs shortest paths; Optimal binary search tree; String editing; Matrix chain product. Week 9: Dynamic Programming: Fundamentals of dynamic programming, dynamic programming for knapsack problem etc. Week 10: Dynamic programming: More examples on dynamic programming. Week 11: Greedy Technique: Knapsack Problem; Minimum spanning tree; Single source shortest paths; Job sequencing with deadlines; Activity selection problem. Week 12: Greedy Technique: More examples using greedy techniques. Week 13: Iterative Improvement; The simplex method; Maximum flow problem; Maximum matching in bipartite graphs. Week 14: Complexity Classes: Basic definitions; P, NP ve NP-Complete classes; NP-Complete problems. Week 15*: Complexity Classes: Basic definitions; P, NP ve NP-Complete classes; NP-Complete problems. Week 16*: Final exam Textbooks and materials: Anany Levitin, "Introduction to The Design and Analysis of Algorithms", Addison WesleyJon Kleinberg, Eva Tardos, "Algorithm Design", Pearson. Recommended readings: Cormen, Leiserton, Rivest, Introduction to Algorithms, MIT Press, 2001.Horowitz, Sahni, Rajasekaran, Computer Algorithms, Computer Science Press, 1998. Sahni, Data Structures, Algorithms, and Applications in C++, McGraw-Hill, 1998.Weiss, Data Structures and algorithm and Algorithm Analysis in C, Addison Wesley, 1997. * Between 15th and 16th weeks is there a free week for students to prepare for final exam.
 Assessment Type of Assessment Week number Weight (%) Mid-terms: 7 35 Other in-term studies: 0 Project: 0 Homework: 3,7,10,12,14 30 Quiz: 0 Final exam: 16 35 Total weight: (%)
 Workload Activity Duration (Hours per week) Total number of weeks Total hours in term Courses (Face-to-face teaching): 3 14 Own studies outside class: 1 14 Practice, Recitation: 0 0 Homework: 3 6 Term project: 0 0 Term project presentation: 0 0 Quiz: 0 0 Own study for mid-term exam: 8 2 Mid-term: 2 2 Personal studies for final exam: 8 1 Final exam: 3 1 Total workload: Total ECTS credits: * * ECTS credit is calculated by dividing total workload by 25. (1 ECTS = 25 work hours)
-->