CSE450 - Design & Analysis of Algorithms





Lecture T, Th 10:30 am - 11:45 am Tempe - CAVC359
Instructor Sandeep Gupta
Office BY548
Office hours T Th 9:00 am - 10:00 am
Email Sandeep.Gupta@asu.edu
Teaching Assistant Prajwal Paudyal
Office Hours NA
Email NA
Teaching Assistant Madhurima Pore
Office Hours BYENG 523 Wednesday 12 noon to 1:00 pm or by email appointment
Email mpore@asu.edu


CONTENTS

ANNOUNCEMENTS


COURSE SYLLABUS in blackboard

COURSE DESCRIPTION
Design and analysis of computer algorithms using analytical and empirical methods; complexity measures, design methodologies, and survey of important algorithms.



Course Work and Tentative breakdown of grades

  • A student will earn a grade on A-E +/- grading scale based on the overall performance in the course. The course will involve Programming and written assignments, Course Program, Midterm and Final exam, as well as Quizzes and Class presentations and Class participation. Details will be provided during the semester. Some important dates and comments are as noted below
  • Homework/Programming Assignments: 4-5: 500 points (approx.)
  • Midterm Exam: 1 Midterm worth 200 points Date: TBA
  • Project/Term Paper or Finals: 300 points
  • Final Exam: Tuesday, December 5, 9:50 - 11:40 AM (Please verify in ASU Final Exam Schedule)
  • Project Teams: Up to 3 people
  • Quizzes: Throughout the semester. Some may be un-announced. Total of 100 points. No makeups, will drop the lowest two.
  • Weightage: This course follows the following philosophy “Each point earned is equally weighted”. Hence the final grade will be based on Total points earned/Total points assigned.
  • Cutoff based on instructors discretion. But in general to get an A overall score should be above 90% of the total.. Extra credit work may be assigned


PRE-REQUISITE

Computer Science BS or Computer Systems Engineering BSE major; CSE 310 with C or better OR Computer Engineering graduate student; Credit is allowed for only CSE 450 or CSE 551



TOPICS

Week Date Topic Materials Lecture Notes
1 08/17 Introduction 1. Introduction Slides
2. Introduction to Algorithms
8/22 Stable Matching Proof handout 1. Stable Matching ALgorithm
2. Demo Slides
2 8/24 Proof of Gale Shapley Alg. 1. Proof of Algorithm
08/29 Understanding Gale Shapley 1. GS Optimality and Extensions
3 08/31 5 Representative Problems and revision of Algorithm (Graphs and Trees) 1. 5 Representative Problems, Analysis of Algorithms
2. Analysis of Algorithms, Graphs
09/05 Discussed Quiz 5 in class
4 09/07 1. 5 Representative Problems
2. Graph Connectivity

5 representative problem
Graph connectivity
09/12 Greedy Algorithms Greedy Alg. 1
5 NA/NA
NA/NA
6 NA/NA
NA/NA
7 NA/NA
NA/NA
8 NA/NA
NA/NA
9 NA/NA
NA/NA
10 NA/NA
NA/NA
11 NA/NA
NA/NA
12 NA/NA
NA/NA
13 NA/NA
NA/NA
14 NA/NA
NA/NA
15 NA/NA
NA/NA
15 NA/NA


BOOKS

Course textbook
Reference books
POLICY ON CHEATING

Any incidence of cheating in this class will be severely dealt with. This applies to homework assignments, programming assignments, quizzes and tests. The minimum penalty for cheating will be that the student will not obtain any credit for that particular assignment. (This means that if in a test and/or assignment a student is found have cheated, he/she will obtain zero in that test and/or assignment.) For the homework and the programming assignments students may discuss the problems with others, but one is expected to turn in the results of one's own effort (not the results of a friend's efforts). One tends to get very suspicious if two identically wrong results show up in the homework assignment and/or tests. The names of the offenders will be maintained in the departmental files. The repeat offenders may be debarred from the University.









Home | Projects | People | Publications | Courses | Resources | Contact