SOLUTION: Data Structures & Algorithms (L5) | My Assignment Tutor

Department of Information Technology Page 1 of 4ICON College of Technology and ManagementPearson BTEC HND in Computing (RQF)Unit 19: Data Structures & Algorithms (L5)Schedule of WorkThis unit is aimed at achieving the following learning outcomes:LO1: Examine abstract data types, concrete data structures and algorithms.LO2: Specify abstract data types and algorithms in a formal notation.LO3: Implement complex data structures and algorithms.LO4: Assess the effectiveness of data structures and algorithms. SessionIndicative ContentsActivityWeek 1LO1Introduction to the unit contents, assessment typesSpecification of ADTs with formal notationActivities:• Group discussion on ADTs and the value of formalspecification of ADTs.• Group activity: Find examples where an ADT is required for agiven task.• Show video of ADT specification case study.• Introduce ADTs as methodical approach to data representationanalysis in a systems development.• Activity: Identification of ADT semanticsLectureGroup discussionSeminarAcademic writingWeek 2LO1Data structuresActivities:• Group discussion on data structures including array, set, stack,queue, list, tree and active, passive and recursive types.• Group activity: Finding examples and situations of use ofarrays and trees.• Show video of importance of appropriate use of datastructures.• Activity: In what ways can variable data structures bedeveloped effectively?Activity: Students to review their own knowledge by identifyingspecific data structures for given tasks.Algorithm typesActivities:• Discuss the importance of recursive, backtracking, dynamic,divide and conquer, branch and bound, greedy, randomisedand brute force algorithms.• Activity: Working in groups discuss key aspects of algorithmtypes and applications.LectureGroup discussionSeminarAcademic writingProviding course workWeek 3LO1AlgorithmsActivities:• Identify and provide examples of sort, quicksort, merge, heap,bucket, selection, search linear, binary, binary search tree,recursive (e.g. binary tree traversals) and find path (e.g.travelling salesman).• Discuss the purpose of sort, quicksort, merge, heap, bucket,selection, search linear, binary, binary search tree, recursive(e.g. binary tree traversals) and find path (e.g. travellingsalesman).• Compare different sort algorithms, explaining their limits andperformance.LectureSeminarGroup discussionQ/AsAcademic writing Department of Information Technology Page 2 of 4 • Group activity: Make a scenario where an algorithm needs tobe developed for a given application.• Group activity: Identify and discuss search algorithms.Week 4LO2Design specificationActivities:• Explore specification of ADTs using formal notation (e.g.ASN.1). Explain ASN.1 specification language providingexamples of developing ADTs.• Activity: Engage students in developing ADTs using ASN.1.Use non-executable program specification language (e.g. SDL, VDM)Activities:• Explore key features of SDL system specification usingexamples and explaining how reduction/inheritance techniquescan be exercised.• Explain how VDM program specification language can be usedto specify pre/post conditions for all paths.• Activity: Students to develop a VDM specification for a givenprogramLecturePracticeGroup discussionFormative Feedback forLO1Week 5LO2Program issuesActivities:• Discuss the need to manage complexity in softwaredevelopment including design patterns, parallelism, interfaces,encapsulation, information hiding and efficiency.• Activity: Students to implement a finite state machinespecification for a given task.Algorithm developmentActivities:• Introduce the notion of algorithm pre-conditions, postconditions and error-conditions. Discuss how error conditionscan be handled using defensive programming.• Activity: Students to investigate how exception handling can beused for a given application.LecturePracticeGroup discussionWeek 6LO2Activities:• Discuss, using examples, how an algorithm might beparallelised for a given task.PracticeGroup discussionAssignment writingFormative Feedback forLO2Week 7LO3Implementation of data structuresActivities:• Introduce students to implementation of multidimensionalarrays, linked lists, stacks, queues, trees, hash table, heap andgraph.• Discuss constructs in high level programming languages toimplement data structures.• Activity: Group debates. Topics can be selected by eachgroup, researched and debated by each team member. Thedebate should discuss the challenge of using primitive datastructures to create complex data structures.Algorithms: sorting, searching, tree traversal, list traversal, hashfunctions, string manipulation, scheduling and recursive algorithmsActivities:• Group discussion of sorting, searching, tree traversal, listtraversal, hash functions, string manipulation, scheduling andrecursive algorithms.• Discuss where these algorithms could be employed.• Group activity: Research and compare types of sortingalgorithms.LectureGroup discussionSeminarIndividual researchactivitiesQuizWeek 8LO3Using handle, pointer, class, methodsActivities:LectureGroup discussionSeminarQ/As Department of Information Technology Page 3 of 4 • Discuss the importance of using handle, pointer, class andmethods to access data structures.• Explain using an implementation language example, howcaution must be exercised when dealing with pointers.• Activity: Students to investigate how methods can be used toaccess and hide data structures.Using an executable programming languageActivities:• Developer guest speaker to discuss the importance of usingpointers when designing data driven programs.• Activity: Students to ask questions to speaker.Week 9LO3Activities:• Introduce students to various examples of algorithms andsupporting data structures showing their appropriateness forthe task.• Activity: Research how parallelism can be introduced intoalgorithm design.PracticeGroup discussionAssignment writingFormative Feedback forLO3Week 10LO4Use of data structure libraries (DSL) and the limitations of DSLActivities:• Introduce students to data structure libraries and how they canreduce the algorithm development time• Activity: Produce a report on the limitations of DSL libraries.• Group activity: Discuss the importance of developing/using asuite of DSL libraries on code reuse.Manual selection of data structures and theoretical analysisActivities:• Introduce methods to manually select data structures.• Group activity: Discuss the use of algorithm manual selectionand algorithm requirements.LectureGroup discussionSeminarQ/AsWeek 11LO4Asymptotic analysis, size of N and Big O notationActivities:• Introduce the concept of asymptotic analysis and Big Onotation.• Discussion how algorithm complexity can be measured.• Introduce the importance of size of N.• Group activity: Evaluate the complexity of a given algorithmusing asymptotic analysis.Algorithm effectivenessActivities:• Introduce the notion of algorithm effectiveness and how tomeasure using run time benchmarks, compiler/interpreterdependencies, resource usage, degree of parallelism, time,space, power performance and efficiency of garbagecollection.• Activity: For a give algorithm produce a report of how thealgorithm performance could be improved, suggesting degreeof improvement.LectureGroup discussionQ/AsWeek 12LO4LO1 -4• Practical session to show how, using a multi-threadedexecutable implementation language running on a parallelarchitecture, an algorithm can be sliced to achieve higherlevels of performance.• Consider the assessment requirements, review progress ingathering examples and plan for completion of theassessment.PracticeAssignment writingWeek 13Presentation on coursework if it is necessaryStudents supportFormative feedbackWeek 14Study week and preparations for assignment submission and ExamsStudents supportWeek 15Students support Department of Information Technology Page 4 of 4Recommended readingBooksCormen, T. (1990) Introduction to Algorithms. MIT Labs.Cormen, T. (2002) Instructors Manual: Introduction to Algorithms. MIT Labs.Heineman, G. (2009) Algorithms in a Nutshell. O’Reilly Publishing.Larmouth, J. (1999) ASN.1 Complete. Kaufman Publishing.Leiss, E. (2007) A Programmer’s Companion to Algorithm Analysis. Chapman & Hall.Sedgewick, R. (1983) Algorithms. Addison-Wesley.Wirth, N. (2004) Algorithms and Data Structures. Oberon.JournalsThe Institute of Engineering and Technology (IET)British Computer Society (BCS)WebsitesHN Global | BTEC Higher Nationals at https://www.highernationals.com/hn-globalwww.cisco.comAcademic Writing BooksBailey, S. (2011), Academic Writing – A Handbook for International Students, London, RoutledgeBurns, T. and Sinfield, S (2016), Essential Study Skills: The Complete Guide to Success at University, Los Angeles,SAGESwales, J. M and Feak, C, B. (2012), Academic Writing for Graduate Students, Ann Abor, The University of Michigan