Analysis of Algorithms
Analysis of Algorithms CECS 428
Popular in Course
Popular in Computer Science and Engineering
This 6 page Class Notes was uploaded by Zackary Cronin on Monday October 5, 2015. The Class Notes belongs to CECS 428 at California State University - Long Beach taught by Darin Goldstein in Fall. Since its upload, it has received 49 views. For similar materials see /class/218748/cecs-428-california-state-university-long-beach in Computer Science and Engineering at California State University - Long Beach.
Reviews for Analysis of Algorithms
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/05/15
1 CECS 428 Analysis of Algorithms Spring 2009 Darin Goldstein Contact info Instructor Darin Goldstein Phone 5629851507 Email dgoldste csulbedu Of ce ECS 546 Phone 5629851507 Email dgoldste csulbedu Of ce hours MW 600630pm TTh 300330 pm 600630 pm HOW ever expect to be kicked out of my of ce 5 minutes beforehand so that I can make it to class on time You Will have priority during the of ce hours just before lecture Web page httpWWWcecscsulbeduNdaring Many of the lectures for this class come from the CECS 528 material and can be found by navigating to their page You can nd them by looking at the syllabus at the end of this handout Textbook Introduction to Algorithms Cormen Leiserson Rivest and Stein McGraWHill 2001 Edition 2 2 Course Description Credits Credit for this course syllabus7 course materials7 etc all 2 go to Todd Ebert the course coordinator for CECS 428 1 Course Objectives 0 Mathematical functions and analysis techniques an ability to use direct indirect and inductive proof strategies knowledge of basic mathematical functions such as ceiling oor log exponentials roots and series Master method and recurrences an ability to solve recurrence relations using recurrence trees and the Master methodi Basic understanding of the Master Theoremi Asymptotic Analysis 7 Compare two growth rates determining if one is smaller than equal to or greater than another determine when a growth rate is poly nomial7 superpolynomial or exponential 7 Knowledge of bigO notation Sorting 7 Analyze the running time of numerous basic sorting algorithmsi Divide and Conquer Algorithms knowledge of algorithms for order statis tics Dynamicprogramming algorithms 7 An ability to identify when a problem has a dynamicprogramming solution an ability to identify optimal substructures within a prob lemi 7 Knowledge of a variety of problems that can be solved using a dynamic programming solutioni 7V1 1 4LJ II 1 between recur i e ithms and dynamic programming algorithmsi Greedy Algorithms knowledge of a variety of problems that can be solved using a greedy algorithm an ability to prove that a greedy algorithm yields an optimal solution An ability to provide an algorithm in natural language and pseudocode and to establish its correctness via an analytical argument An ability to analytically establish that a given algorithm has some stated propertyi Graph Algorithms 7 Understand the importance of the depth rst search via interesting example algorithms such as Tarjans strongly connected components algorithm and perform these algorithms on examples 7 Perform the FordFulkerson max ow algorithm on examples 7 Perform Prims Kruskals7 and Dijkstras algorithms for minimum spanning trees on examples 7 Perform Dijkstras single source shortest path algorithm on examplesi Understand the reasons behind the necessity for good graph algo rit ms 22 Topics 0 Asymptotic Analysis 0 Mathematical functions and analysis techniques 0 Sorting o Binary Heaps 0 Algorithm Analysis and Complexity 0 Greedy Algorithms 0 Divide and Conquer Algorithms 0 Graph Algorithms 0 Dynamic Programming Algorithms 0 Mathematical Proof Strategies 3 Lectures Some good news for this course is that you will never be explicitly penalized for missing a lecture I will never give any popquizzes that are not announced at least the lecture beforehand You will be noti ed of any graded material other than quizzes at least two weeks in advance or else it will be mentioned somewhere in this page On the other hand this is de nitely a lecturebased course If you choose to miss a lecture I will not penalize you for it or hold it against you in any way but you are fully responsible for any material that I go over lfl mention something in lecture that is not in the book YOU ARE STILL RESPONSIBLE FOR KNOWING IT I will not redo a lecture for people that missed it the rst time It is your responsibility to get the notesinformation If you miss any kind of instructions about assignments that are given during lecture including but not limited to due dates methods for submission for assignments etc it is STILL your responsibility to be aware of what occurred in lecture 4 Grading Examquiz questions are not required to look anything like the homework ques tions Examsquizzes will be given to test whether you are able to APPLY the knowledge that you have learned The policies I follow in terms of grading short answer questions are as follows 0 Partial credit will only be given out for steps LEADING TO THE COR RECT ANSWER The answer itself is meaningless without clear reason ing This means that if your reasoning is incorrect or not explicitly on the page the ANSWER BY ITSELF WILL NOT BE COUNTED AS CORRECT 0 Write out every step of your reasoning If it is not on the page you will not get credit for it Clearly mark out anything you don7t want graded If it is on your page and not crossed out it will be graded as if its part of your answer If there is more than one answer on your page I WILL GRADE THE INCORRECT ANSWER Points will be deducted for anything incorrect written on the page that is not crossed out even if the nal answer is correct For multiple choice questions you are required to get the answer entirely correct In other words if the answer is B an D and you choose only B or BCD or anything other than BD then your answer is incorrect No partial credit is given for multiple choice questions 5 Homework Quizzes Exams Programming As signments Homework will not be turned it However I highly recommend doing it if you want to do well on the exams If you choose not to do the homework you will not be explicitly penalized but you should plan on not doing well in the course The tentative breakdown for grading is as follows 1 Midterm 1 13 2 Midterm 2 13 3 Final Exam 13 The class will be graded on a curve Independent of the curve if you get 90 of the total points or above you get an automatic A 80 of the total points or above you get an automatic B and so on I do not round points The curve can only help your grade Usually independent of the actual score the top personpeople get As I then go down the grades and determine where the rst big break in the grades is and after the rst big break we start the B s This continues all the way down Generally speaking of ce hours are pretty crowded the day before exams I was a college student once and am very familiar with the concept of cramming for an exam During of ce hours I will try to help as many people as I can However the chances are pretty good that if you leave all of your questions for the last minute they may go unanswered Please take this into account when you start your studying 6 Cheating You may not leave the room during any in class exami You may not use any communication device cell phones etc during any in class exami For takehome exams you are allowed to use calculators and any nonhuman help you need If you receive help in any way from any human being including any help at all from the Internet human help using an electronic or other intermediary is still considered human help it will be considered cheating and will be dealt with as outlined belowl If you have any questions about whether or not something is considered human help77 it is your responsibility to come see me before you receive such help You will not receive any leniency after the fact please consider this one of the rare occasions when it is easier to get permission than forgiveness Failure to observe these rules will result in an F in the course Cheating on any graded material in the course will lead to an automatic grade of F in the course I don7t give warnings 7 The nal word If there is anything on this page that you have a question or comment about it is very important to let me know about it on the FIRST DAY OF CLASSES After the rst day of classes I will assume that you are aware of the grading policiesi Any grading misunderstandings you have after the rst day of classes are your responsibility Good luck 8 Syllabus ll Asymptotic Analysis bigolpdf 2 Mathematical functions and analysis techniques recurrencelpdf 3i Sorting bubble insertion selection quicksort randomized quicksort qsort 4i Binary Heaps insertion deletion 39 39 and quot 5i Midterm l 6 Algorithm Analysis and Complexity DandCipdf order statistics with probability 7 Greedy Algorithms greedylpdf without MSTSSSP 8 Divide and Conquer Algorithms DandClpdf order statistics without probability 9 Graph Algorithms DFS FordFulkerson max ow SCC 10 Midterm 2 11 Graph Algorithms MST SSSP 12 Dynamic Programming Algorithms dplipd deipdf 13 Final Exam Midterm 3
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'