ECTS @ IUE ECTS @ IUE ECTS @ IUE ECTS @ IUE ECTS @ IUE ECTS @ IUE ECTS @ IUE

ucuncuduzeymenu.asp

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 Up

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 Up
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 Wesley
Jon 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 Up
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 Up
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)
-->