Unformatted text preview:

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 InformationLecture:James B D JoshiMondays: 3:00-5.50 PMOne (two) 15 (10) minutes break(s)Office Hours: Wed 1:00-3:00PM/AppointmentPre-requisiteone programming languageCourse materialTextbookAlgorithm in C (Parts 1-5 Bundle)- Third Edition by Robert Sedgewick, (ISBN: 0-201-31452-1, 0-201-31663-3), Addison-WesleyReferencesIntroduction 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 outlineIntroduction to Data Structures and Analysis of AlgorithmsAnalysis of AlgorithmsElementary/Abstract data typesRecursion and TreesSorting AlgorithmsSelection, Insertion, Bubble, ShellsortQuicksortMergesortHeapsortRadix sortSearchingSymbol tablesBalanced TreesHashingRadix SearchGraph AlgorithmsGradingQuiz 10% (in the beginning of the class; on previous lecture)Homework/Programming Assignments 40% (typically every week)Midterm 25%Comprehensive Final 25%Course PolicyYour work MUST be your ownZero tolerance for cheating You get an F for the course if you cheat in anything however small – NO DISCUSSIONHomeworkThere will be penalty for late assignments (15% each day)Ensure clarity in your answers – no credit will be given for vague answersHomework is primarily the GSA’s responsibilitySolutions/theory will be posted on the webCheck webpage for everything!You are responsible for checking the webpage for updatesOverviewAlgorithmA problem-solving method suitable for implementation as a computer programData structuresObjects created to organize data used in computationData structure exist as the by-product or end product of algorithmsUnderstanding data structure is essential to understanding algorithms and hence to problem-solvingSimple algorithms can give rise to complicated data-structuresComplicated 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 factorTechnology can improve things by a constant factorGood algorithm design can do much better and may be cheaperSupercomputer cannot rescue a bad algorithmData structures and algorithms as a field of studyOld enough to have basics knownNew discoveriesBurgeoning application areasPhilosophical implications?Simple exampleAlgorithm and data structure to do matrix arithmeticNeed a structure to store matrix valuesUse 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 ConnectivityNetwork ConnectivityNodes at grid pointsAdd connections between pairs of nodesAre 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 AbstractionWhat are the critical operations needed to support finding connectivity?N objects – N can be very largeGrid pointsFIND: test whether two objects are in same setIs A connected to B?UNION: merge two setsAdd a connectionDefine Data Structure to store connectivity information and algorithms for UNION and FINDQuick-Find algorithmData StructureUse an array of integers – one corresponding to each objectInitialize id[i] = iIf p and q are connected they have the same idAlgorithmic OperationsFIND: to check if p and q are connected, check if they have the same idUNION: To merge components containing p and q, change all entries with id[p] to id[q]Complexity analysis:FIND: takes constant timeUNION: 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 AlgorithmData StructureUse an array of integers – one corresponding to each objectInitialize id[i] = iIf p and q are connected they have same rootAlgorithmic OperationsFIND: to check if p and q are connected, check if they have the same rootUNION: Set the id of the p’s root to q’s rootComplexity analysis:FIND: takes time proportional to the depth of p and q in treeUNION: 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-UnionLess computation


View Full Document

Pitt IS 2620 - LECTURE NOTES

Download LECTURE NOTES
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view LECTURE NOTES and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view LECTURE NOTES 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?