Welcome to IS 2610Course InformationCourse materialCourse outlineGradingCourse PolicyOverviewWhy study Data Structures (and algorithms)Simple exampleAnother example: Network ConnectivityNetwork ConnectivityUnion-Find AbstractionQuick-Find algorithmQuick-findComplete algorithmQuick-Union AlgorithmSlide 17Quick-UnionComplexity of Quick-UnionAnalysis of algorithmGrowth of functionsSome common functionsSpecial functions and mathematical notationsBig O-notation – Asymptotic expressionBig-O Notation(f(n)) and (f(n))Basic RecurrencesSlide 28Slide 29Welcome to IS 2610IntroductionCourse InformationLecture:James B D JoshiMondays: 3:00-5.50 PMOne (two) 15 (10) minutes break(s)Office Hours: Wed 1:00-3:00PM/AppointmentPre-requisiteone programming languageCourse materialTextbookAlgorithm in C (Parts 1-5 Bundle)- Third Edition by Robert Sedgewick, (ISBN: 0-201-31452-1, 0-201-31663-3), Addison-WesleyReferencesIntroduction to Algorithms, Cormen, Leiserson, and Rivest, MIT Press/McGraw-Hill, Cambridge (Theory)Fundamentals of Data Structures by Ellis Horowitz, Sartaj Sahni, Susan Anderson-Freed Hardcover/ March 1992 / 0716782502 The C Programming language, Kernigham & Ritchie (Programming)Other material will be posted (URLs for tutorials)Course outlineIntroduction to Data Structures and Analysis of AlgorithmsAnalysis of AlgorithmsElementary/Abstract data typesRecursion and TreesSorting AlgorithmsSelection, Insertion, Bubble, ShellsortQuicksortMergesortHeapsortRadix sortSearchingSymbol tablesBalanced TreesHashingRadix SearchGraph AlgorithmsGradingQuiz 10% (in the beginning of the class; on previous lecture)Homework/Programming Assignments 40% (typically every week)Midterm 25%Comprehensive Final 25%Course PolicyYour work MUST be your ownZero tolerance for cheating You get an F for the course if you cheat in anything however small – NO DISCUSSIONHomeworkThere will be penalty for late assignments (15% each day)Ensure clarity in your answers – no credit will be given for vague answersHomework is primarily the GSA’s responsibilitySolutions/theory will be posted on the webCheck webpage for everything!You are responsible for checking the webpage for updatesOverviewAlgorithmA problem-solving method suitable for implementation as a computer programData structuresObjects created to organize data used in computationData structure exist as the by-product or end product of algorithmsUnderstanding data structure is essential to understanding algorithms and hence to problem-solvingSimple algorithms can give rise to complicated data-structuresComplicated algorithms can use simple data structuresWhy study Data Structures (and algorithms)Using a computer?Solve computational problems?Want it to go faster? Ability to process more data?Technology vs. Performance/cost factorTechnology can improve things by a constant factorGood algorithm design can do much better and may be cheaperSupercomputer cannot rescue a bad algorithmData structures and algorithms as a field of studyOld enough to have basics knownNew discoveriesBurgeoning application areasPhilosophical implications?Simple exampleAlgorithm and data structure to do matrix arithmeticNeed a structure to store matrix valuesUse a two dimensional array: A[M, N]Algorithm to find the largest elementlargest = A[0][0];for (i=0; i < M; i++)for (i=0; i < N; i++)if (A[i][j]>largest) then largest= A[i][j];How many times does the if statement gets executed?How many times does the statement “largest= A[i][j]” gets executed?Another example: Network ConnectivityNetwork ConnectivityNodes at grid pointsAdd connections between pairs of nodesAre A and B connected?ABNetwork ConnectivityIN OUT Evidence3 4 3 44 9 4 98 0 8 02 3 2 35 6 5 62 9 (2-3-4-9)5 9 5 97 3 7 34 8 4 85 6 (5-6)0 2 (2-3-4-8-0)6 1 6 1Union-Find AbstractionWhat are the critical operations needed to support finding connectivity?N objects – N can be very largeGrid pointsFIND: test whether two objects are in same setIs A connected to B?UNION: merge two setsAdd a connectionDefine Data Structure to store connectivity information and algorithms for UNION and FINDQuick-Find algorithmData StructureUse an array of integers – one corresponding to each objectInitialize id[i] = iIf p and q are connected they have the same idAlgorithmic OperationsFIND: to check if p and q are connected, check if they have the same idUNION: To merge components containing p and q, change all entries with id[p] to id[q]Complexity analysis:FIND: takes constant timeUNION: takes time proportional to NQuick-findp-q array entries 3-4 0 1 2 4 4 5 6 7 8 94-9 0 1 2 9 9 5 6 7 8 98-0 0 1 2 9 9 5 6 7 0 92-3 0 1 9 9 9 5 6 7 0 95-6 0 1 9 9 9 6 6 7 0 95-9 0 1 9 9 9 9 9 7 0 97-3 0 1 9 9 9 9 9 9 0 94-8 0 1 0 0 0 0 0 0 0 06-1 1 1 1 1 1 1 1 1 1 1Complete algorithm#include <stdio.h>#define N 10000main(){ int i, p, q, t, id[N];for (i = 0; i < N; i++) id[i] = i;while (scanf(“d% %d\n”, &p, &q) == 2{if (id[p] == id[q]) continue;for (pid = id[p], i = 0; i < N; i++) if (id[i] == pid) id[i] = id[q];printf(“s %d\n”, p, q);}}Complexity (M x N) For each of M union operations we iterate for loop at N timesQuick-Union AlgorithmData StructureUse an array of integers – one corresponding to each objectInitialize id[i] = iIf p and q are connected they have same rootAlgorithmic OperationsFIND: to check if p and q are connected, check if they have the same rootUNION: Set the id of the p’s root to q’s rootComplexity analysis:FIND: takes time proportional to the depth of p and q in treeUNION: takes constant timesComplete algorithm#include <stdio.h>#define N 10000main(){ int i, p, q, t, id[N];for (i = 0; i < N; i++) id[i] = i;while (scanf(“d% %d\n”, &p, &q) == 2{printf(“s %d\n”, p, q);}}Quick-Unionp-q array entries s 3-4 0 1 2 4 4 5 6 7 8 94-9 0 1 2 4 9 5 6 7 8 98-0 0 1 2 4 9 5 6 7 0 92-3 0 1 9 4 9 5 6 7 0 95-6 0 1 9 4 9 6 6 7 0 95-9 0 1 9 4 9 6 9 7 0 97-3 0 1 9 4 9 6 9 9 0 04-8 0 1 9 4 9 6 9 9 0 06-1 1 1 9 4 9 6 9 9 0 031 2 4 5 6 7 8 9031 245 6 7 89031 245 6 7890312 45 6 7890312 456 7890312 4567890312 456 7890312 456 7890312 456 7890Complexity of Quick-UnionLess computation
View Full Document