{"id":511,"date":"2021-09-02T17:56:45","date_gmt":"2021-09-02T17:56:45","guid":{"rendered":"https:\/\/itgeeks.in\/home\/?p=511"},"modified":"2021-09-02T20:46:00","modified_gmt":"2021-09-02T20:46:00","slug":"2k6cs-702-design-and-analysis-of-algorithms","status":"publish","type":"post","link":"https:\/\/itgeeks.in\/home\/?p=511","title":{"rendered":"2K6CS 702 DESIGN AND ANALYSIS OF ALGORITHMS"},"content":{"rendered":"\n

Module I (12 hours)<\/strong>
Role of algorithms in computing \u2013 RAM model \u2013 growth of functions \u2013 asymptotic notations (Big-Oh, Little-Oh, Big omega, Little omega, Theta)- solution to recurrences \u2013 substitution method-recursion treemastertheorem (proof not expected)-Analysis of sorting algorithms \u2013 merge sort, heap sort, quick sort- Analysis of string matching algorithms -KMP algorithm. Amortized Analysis \u2013Aggregate \u2013Accounting \u2013Potential Methods
Module II (14 hours)<\/strong>
Different approaches to algorithm design: Divide and conquer \u2013 Strassens matrix multiplication \u2013MedianFinding-Greedy method \u2013 Huffman code-Minimum cost spanning tree-Kruskals and Prims algorithm-Dynamic programming \u2013Optimal binary search tree\u2013 Chain matrix multiplication Back tracking \u2013 Queens problem\u2013Branch and bound-assignment problem-TSP
Module III (12 hours)<\/strong>
Complexity: complexity classes \u2013 P,NP,Co-NP, NP-hard and NPC problems \u2013 cooks theorm (proof notexpected) \u2013 NP completeness reductions for clique \u2013 vertex cover \u2013 subset sum \u2013 Hamiltonian cycle \u2013 TSPapproximationalgorithms \u2013 vertex cover \u2013 TSP \u2013 set covering and subset sum
Module IV (14 hours)<\/strong>
Randomized algorithms: Some complexity classes randomized algorithm for n-Queen , Quick sort-Probabilistic algorithms: pseudo random number generation methods – Monte Carlo algorithms -probabilistic counting – verifying matrix multiplication – primality testing – miller rabin test – integerfactorization – Dixon\u2019s integer factorization algorithm -Pollard\u2019s rho heuristic amplification of stochasticadvantage – Les Vegas algorithms.
 <\/p>\n\n\n\n

Text books<\/strong>
1. Corman T H, Lieserson C E & Rivest R L, Introduction to Algorithms, PHI<\/a>
2. Motwani R & Raghavan P, Randomized algorithms, Cambridge university press<\/a>
3. Gilles Brassard, Paul Bratley, \u201cFundamentals of Algorithms\u201d, PHI<\/a>
Reference books<\/strong>
1. Basse S, Computer Algorithms : Introduction to design and analysis, Addison Wesley
2. S K Basu , Design methods and analysis of algorithms, PHI
3. Berman and Paul, \u201cAlgorithms\u201d,Cenage Learning Indian Edition<\/p>\n\n\n\n

\n
Question Papers<\/a><\/div>\n\n\n\n
Notes<\/a><\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

Module I (12 hours)Role of algorithms in computing \u2013 RAM model \u2013 growth of functions \u2013 asymptotic notations (Big-Oh, Little-Oh,<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[26,22,9,8],"tags":[7],"class_list":["post-511","post","type-post","status-publish","format-standard","hentry","category-ku-s7-cse","category-ku-syb-s7","category-ku-syllabus","category-syllabus","tag-kannur-university"],"_links":{"self":[{"href":"https:\/\/itgeeks.in\/home\/index.php?rest_route=\/wp\/v2\/posts\/511","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/itgeeks.in\/home\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/itgeeks.in\/home\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/itgeeks.in\/home\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/itgeeks.in\/home\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=511"}],"version-history":[{"count":3,"href":"https:\/\/itgeeks.in\/home\/index.php?rest_route=\/wp\/v2\/posts\/511\/revisions"}],"predecessor-version":[{"id":632,"href":"https:\/\/itgeeks.in\/home\/index.php?rest_route=\/wp\/v2\/posts\/511\/revisions\/632"}],"wp:attachment":[{"href":"https:\/\/itgeeks.in\/home\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=511"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/itgeeks.in\/home\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=511"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/itgeeks.in\/home\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=511"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}