Six Phrase

Engineering

Data Structure & Algorithm Expert – 7 Semester – Technical Training Program Syllabus

Cambridge English Program

English Competency Development Training

Speak the language of your customer, create memorable experiences and drive sales. Your career and future business are prone to grow only with language development. We, at Six Phrase, tailor the content focusing on your future business needs, and you can measure your success with our special communication courses.

At Six Phrase, you are exposed to a variety of accents and speakers, as well as a range of colloquial and idiomatic language in context. Also, our special training on English Competency Development (ECD) and Cambridge English Training (BEC, YLE, KET, PET, FCE, BULATS, IELTS) assures you with a ray of hope for a future you have always dreamt of.

Technical Training Program Syllabus

Training – 45 to 90 Hours per Semester of Technical Training.
AI Enabled LMS (Learning Management System) & Talent Hiring Platform based on EMPLOYABILITY INDEX SCORE (EIS).
Hiring – Marquee (salary > 20lakhs per annum), Super Dream (salary 10 lakhs to 20lakhs per annum), Dream (salary 5 lakhs to 10lakhs per annum), and Service (salary < 5 lakhs per annum) Companies Placements.
- Opportunity 1: During our training program enroll students in MySlate LMS. Follow up and motivate students to complete the courses in LMS. Award reward points (EMPLOYABILITY INDEX SCORE) for each problem/program a student solves in the LMS. Categorize Talent in 7th Semester based on scores accumulated (EMPLOYABILITY INDEX SCORE) in our LMS. Place students in Marquee, Super Dream, Dream & Services companies based on scores accumulated.
  Outcome based placements based on below target.
  EMPLOYABILITY INDEX SCORE.
  - Marquee Students >25000 points
  - Super Dream Students >20000 && <25000 points
  - Dream Students >15000 && <20000 points
  - Service Students >12000 && <15000 points
- Opportunity 2: Identify Special Talent in 7th Semester based on Employability Index Score accumulated in our LMS. Train the identified students on Future Skills (AI, ML, DS, Big Data, Cloud, Cyber Security, Full Stack etc…) and Deploy them. Students will not be charged for Future Skills Training.
- Opportunity 3: Identify Talent who wish to Upgrade their existing service offer to product offer at the end of 7th or beginning of 8th Semester (after Day1 placements). Train them on Future Skills and Deploy them. Students will not be charged for Future Skills Training.
- Opportunity 4: Identify Unplaced & Deserving Talent at the end of 7th or beginning of 8th Semester (after Day1 placements). Hire them with a Stipend of 15k to 20k per month and train the students for services companies and Deploy them.

SEMESTER – I

Problem Solving Using C Programming

Course Objectives

The course aims to provide exposure to problem-solving through programming. It aims to train the student to the basic concepts of the C-programming language. This course involves a lab component which is designed to give the student hands-on experience with the concepts.

Course Outcomes

Upon completion of this course, the students will be able to:

Identify situations where computational methods and computers would be useful.
Given a computational problem, identify and abstract the programming task involved.
Approach the programming tasks using techniques learned and write pseudo-code.
Choose the right data representation formats based on the requirements of the problem.
Use the comparisons and limitations of the various programming constructs and choose the right one for the task in hand.
Write the program on a computer, edit, compile, debug, correct, recompile and run it.
Identify tasks in which the numerical techniques learned are applicable and apply them to write programs, and hence use computers effectively to solve the task.

UNIT 1: Introduction To Principles Of Programming:

Introduction to Programming , Programing Domain : Scientific Application , Business Applications, Artificial Intelligence, Systems Programming , Web Software Categories of Programming Languages: Machine Level Languages, Assembly Level Languages , High Level Languages Programming Design Methodologies : Top Down and Bottom UP Program Development Cycle with case study, Program Execution and Translation Process ,Problem solving using Algorithms and Flowcharts, Performance Analysis and Measurements: Time and Space complexity.

UNIT 2: Introduction To C Programming:

Features of C and its Basic Structure, Simple C programs, Constants, Integer Constants, Real Constants, Character Constants, String Constants, Backslash Character Constants, Concept of an Integer and Variable, Rules for naming Variables and assigning values to variables, Floating-point Numbers, Converting Integers to Floating-point and vice-versa, Mixed-mode Expressions, The type cast Operator, The type char, Keywords, Character Input and Output, Formatted input and output, The gets() and puts() functions, Interactive Programming.

UNIT 3: Operators, Expressions And Control Statements:

Arithmetic Operators, Unary Operators, Relational and Logical Operators, The Conditional Operator, Library Functions, Bitwise Operators, The Increment and Decrement Operators, The Size of Operator, Precedence of operators, The goto statement, The if statement, The if-else statement, Nesting of if statements, The conditional expression, The switch statement, The while loop, The do…while loop, The for loop, The nesting of for loops, The break statement and continue statement.

UNIT 4: Arrays, Strings And Pointers:

One Dimensional Arrays, Passing Arrays to Functions, Multidimensional Arrays, Strings, Basics of Pointers, Pointers and One-dimensional Arrays, Pointer Arithmetic, Pointer Subtraction and Comparison, Similarities between Pointers and One-dimensional Arrays, Null pointers, Pointers and Strings, Pointers and two-dimensional arrays, Arrays of Pointers.

UNIT 5: Structures, Unions And Functions:

Basics of Structures, Arrays of Structures, Pointers to Structures, Self-referential Structures, Unions, Function Philosophy, Function Basics, Function Prototypes, and Passing Parameters: Passing Parameter by value and Passing Parameter by reference, passing string to function, Passing array to function, Structures and Functions Recursion.

References:

Programming in ANSI C – Balagurusamy – Tata McGraw-Hill Education, 2008.
Programming in C (3rd Edition), by Stephen G. Kochan, Sams, 2004.
Programming in C – Stephen G. Kochan, III Edition, Pearson Education.

SEMESTER – II

Advanced C Programming

Course Objectives

The course is oriented to those who want to advance structured and procedural programming understating and to improve C programming skills. The major objective is to provide students with understanding of code organization and functional hierarchical decomposition with using complex data types..

Course Outcomes

Upon completion of this course, the students will be able to:

Understanding a functional hierarchical code organization.
Ability to define and manage data structures based on problem subject domain.
Ability to work with textual information, characters and strings.
Ability to work with arrays of complex objects.
Understanding a concept of object thinking within the framework of functional model.
Understanding a concept of functional hierarchical code organization.
Understanding a defensive programming concept. Ability to handle possible errors during program execution.

UNIT 1: Introduction To Recursion:

Introduction to Recursion, Types of Recursion – Head Recursion , Tail Recursion, Tree Recursion, Indirect Recursion and Nested Recursion . Recursion vs Looping – Analysis on efficiency of looping and recursion, Working of recursive code in main memory. Recurrence Relation , Different types of recurrence relation. Deriving time complexity and space complexity using recurrence relation.

UNIT 2: Growth Functions And Recursion:

Polynomial Equations, Compare growth functions – order growth functions, omega growth functions, theta growth functions – Constant time, Linear time, Logarithmic time, Quadratic time and exponential time . Problems on Recursions – Factorial Number, Sum of first N Natural Numbers, Nth Fibinocci Number, Exponent Function, Taylor Series, Tower of Hanoi.

UNIT 3: Storage Classes, The Preprocessor And Dynamic Memory Allocation:

Storage Classes and Visibility, Automatic or local variables, Global variables, Static variables, External variables, File Inclusion, Macro Definition and Substitution, Macros with Arguments, Nesting of Macros, Conditional Compilation, Dynamic Memory Allocation, Allocating Memory with malloc, Allocating Memory with calloc, Freeing Memory, Reallocating Memory Blocks, Pointer Safety, The Concept of linked list, Inserting a node by using Recursive Programs, Sorting and Reversing a Linked List, Deleting the Specified Node in a Singly Linked List.

UNIT 4: File Management:

Defining and Opening a file, Closing Files, Input/output Operations on Files, Predefined Streams, Error Handling during I/O Operations, Random Access to Files, Command Line Arguments.

UNIT 5: Bit Manipulation:

The hexadecimal number system, C bitwise operators, Working with individual bits, How to check if a given number is a power of 2, Count the number of ones in the binary representation of the given number, Check if the ith bit is set in the binary form of the given number, How to generate all the possible subsets of a set, Find the largest power of 2 (most significant bit in binary form), which is less than or equal to the given number N, Tricks with Bits, Applications of bit operations.

References:

R. G. Dromey, “How to Solve It By Computer”, Pearson, 1982
A.R. Bradley, “Programming for Engineers”, Springer, 2011
Kernighan and Ritchie, “The C Programming Language”, (2nd ed.) Prentice Hall, 1988

SEMESTER – III

Problem Solving using Basic Data Structures

Course Objectives

The objective of the course is to familiarize students with basic data structures and their use in fundamental algorithms.

Course Outcomes

Upon completion of this course, the students will be able to:

Data abstraction and information hiding.
linear data structures and their applications in problem solving and programming.
Nonlinear data structures and their applications in problem solving and programming.
Internal and external sort and search techniques.

UNIT 1: Linked List & Stack:

Linked List – Singly Linked List, Structure, Node creation, Singly Linked List Representation, Singly Linked List Traversal, Doubly Linked List – Structure, Node creation, Doubly Linked List Representation, Doubly Linked List Traversal, Circular Linked List, Structure, Node creation, Circular Linked List Representation, Circular Linked List Traversal Stack, Stack – Introduction Push, Pop, Peek or Top, isEmpty() and isFull(), Time Complexities of the Operations, Applications of Stack Balancing of symbols, Infix to Postfix/Prefix Conversation, Stock Span Problem, Histogram Problem, Implementation – Using Array, Using Linked List

UNIT 2: Queue & Heap:

Queue – Introduction – EnQueue, Applications of Queue Data Structure, Priority Queue, Applications of Priority Queue, Deque, Circular Queue, Implementation – Queue using Stack, LRU cache Implementation, Stack using queue, Heap – Binary Heap, Complete Binary Tree, Tree Representation of Binary Heap, Max Binary Heap, Min Binary Heap, Insertion and Deletion in Binary Heap, Heap Sort, Application of Binary Heap.

UNIT 3: Binary Tree:

Binary Tree – Introduction, What is Tree?, Representation of Tree, Properties and Terminologies of Binary Tree, Types of Binary Tree Full ,Complete,Perfect and Balanced Tree, Degenerate or pathological Tree, Binary Search Tree, Insertion and Deletion, Inorder , Preorder , PostOrder and LevelOrder Traversal

UNIT 4: Trees And Hashing:

Hashing – Hashing Techniques, Hashing Introduction, Linear Probing for Collision Handling, Separate Chaining for Collision Handling, Open Addressing for Collision Handling, Union and Intersection of two Linked Lists. AVL Tree Left-Left, Left-Right, Right-Right and Right-Left Imbalance, Left and Right Rotation, AVL with duplicate keys, Implementation – Red Black Tree, Rules of coloring in Red-black Tree, Left and Right Rotation, Implementation of Insertion and Deletion

UNIT 5: Graph:

Graph terminology –Representation of graphs –Path matrix –Graph Traversal –BFS (breadth first search) –DFS (depth first search) –Minimum spanning Tree –Kruskal’s Algorithm & Prim’s Algorithm –Warshall’s algorithm (shortest path algorithm).

References:

Weiss, Mark. A. (2012), Data structures and algorithm analysis in Java. 3 edition. Harlow, Essex : Pearson (632 p).
Zobel, Justin (2014), Writing for Computer Science. 3 edition. Springer Verlag London Ltd (270 p).

SEMESTER – IV

Basic Design and Analysis of Algorithms

Course Objectives

This course assumes that students know how to analyze simple algorithms and data structures. It introduces students to the design of computer algorithms, as well as analysis of sophisticated algorithms.

Course Outcomes

Upon completion of this course, the students will be able to:

Analyze the asymptotic performance of algorithms.
Write rigorous correctness proofs for algorithms.
Demonstrate familiarity with major algorithms and data structures.
Apply important algorithmic design paradigms and methods of analysis.
Synthesize efficient algorithms in common engineering design situations.

UNIT 1: Introduction To Algorithms:

Analysis of Algorithms – Asymptotic Analysis, Worst, Average and Best Cases, Asymptotic Notation, little o, and little omega notations, Lower and Upper Bound Theory, Analysis of Loops, Solving Recurrences, Amortized Analysis, What does ‘Space Complexity’ mean?, Pseudo-polynomial Algorithms, NP-Completeness Introduction, Polynomial Time Approximation Scheme, A Time Complexity Question, Time Complexity of building a heap, Time Complexity where loop variable is incremented by 1, 2, 3, 4 .., Time Complexity of Loop with Powers, Performance of loops (A caching question).

UNIT 2: Searching And Sorting:

Searching – Linear Search, Binary Search, Jump Search, Interpolation Search, Exponential Search, Ternary Search, Sorting – Selection Sort, Bubble Sort, Insertion Sort, Merge Sort, Heap Sort, QuickSort, Radix Sort, Counting Sort, Bucket Sort, ShellSort, Comb Sort, Pigeonhole Sort, Cycle Sort, Interpolation search vs Binary search, Stability in sorting algorithms, Lower bound for comparison-based sorting algorithms, Merge Sort for Linked Lists, Iterative Quick Sort, QuickSort on Singly Linked List, QuickSort on Doubly Linked List, A Problem in Many Binary Search Implementations, Sort an array in waveform, Why is Binary Search preferred over Ternary Search?

UNIT 3: Backtracking:

Print all permutations of a given string and number, Knight’s Tour Plan, Rat in a Maze, N Queen Problem, Subset Sum, m-Coloring Problem, Hamiltonian Cycle, Sudoku, Tug of War.

UNIT 4: Branch And Bound:

Introduction with 0/1 Knapsack, Implementation of 0/1 Knapsack, 8 puzzle Problem, Job Assignment Problem, N Queen Problem, Traveling Salesman Problem.

UNIT 5: Misc, Divide And Conquer:

Misc -Sieve of Eratosthenes, Sieve of Sundaram, Fermat Little Theorem, Even Fibonacci Series. Divide and Conquer – Median of two sorted arrays, Count Inversions, Closest Pair of Points, Strassen’s Matrix Multiplication.

References:

“Introduction to Algorithms” by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
“Algorithms Unlocked” by Thomas H. Cormen.

SEMESTER – V

Advanced Data Structures

Course Objectives

The objective of the course is to familiarize students with basic data structures and their use in fundamental algorithms.

Course Outcomes

Upon completion of this course, the students will be able to:

Data abstraction and information hiding.
linear data structures and their applications in problem solving and programming.
Nonlinear data structures and their applications in problem solving and programming.
Internal and external sort and search techniques.

UNIT 1: Segment Tree:

Segment Tree – Sum of given Range, Representation of Segment Tree for Sum Range Query, Implementation of Sum Range Query, Minimum Range Query, Representation of Segment Tree for Minimum Range Query, Implementation of Minimum Range Query. Lazy Propagation in Segment Tree – Introduction, Implementation,. Persistent Segment Tree – Introduction, Implementation.

UNIT 2: Trie, Suffix Array And Suffix Tree:

Trie – Introduction, Representation of Trie, Operations – Insert , Search and Delete, Implementation, Longest Prefix Matching, Print unique rows in a given boolean matrix, Suffix Array and Suffix Tree, Suffix Array – Introduction, nLogn Algorithm, Kasai’s Algorithm for Construction of LCP array from Suffix Array, Suffix Tree – Introduction , Ukkonen’s Suffix Tree Construction, Generalized Suffix Tree, Creating a Linear time Suffix Array using Suffix Tree, Substring Check, Searching All Patterns, Longest Repeated Substring, Longest Common Substring

UNIT 3: Splay Tree And B – Tree:

Splay Tree – Introduction, Representation of Splay Tree, Operations – Insert , Search and Delete, Implementation – B Tree, Introduction, Disk Structure, Level Indexing, Multi-Level Indexing, Implementation, Insertion and Deletion in B Tree.

UNIT 4: Graph I:

Graph – Introduction, Graph and its Representations, Breadth First Traversal for a Graph, Depth First Traversal for a Graph, Implementation – Topological Sorting, BiPartite Graph, Snake and Ladder Problem, Spanning Tree – Minimum Spanning Tree using Kruskal Algorithm, Minimum Spanning Tree using Prim’s Algorithm, Boruvka’s Algorithm for Minimum Spanning Tree, Steiner Tree

UNIT 5: Graph II:

Graph Cycle – Detect cycle in Directed and Undirected graph, Longest Path in a Directed Acyclic Graph, Disjoint set or Union Find, Union Find Algorithm ( Union By Rank and Find by Optimized Path Compression ), Shortest Paths – Dijkstra’s shortest path Algorithm, Bellman-Ford Algorithm, Floyd Warshall Algorithm, Johnson’s Algorithm for All-pairs shortest paths, Maximum Flow – Ford-Fulkerson Algorithm for Maximum Flow Problem, Find minimum s-t cut in a flow network, Maximum Bipartite Matching, Karger’s Algorithm, Dinic’s Algorithm.

References:

Weiss, Mark. A. (2012), Data structures and algorithm analysis in Java. 3 edition. Harlow, Essex : Pearson (632 p).
Zobel, Justin (2014), Writing for Computer Science. 3 edition. Springer Verlag London Ltd (270 p).

SEMESTER VI

Advanced Design and Analysis of Algorithms

Course Objectives

Course Outcomes

Upon completion of this course, the students will be able to:

Analyze the asymptotic performance of algorithms.
Write rigorous correctness proofs for algorithms.
Demonstrate familiarity with major algorithms and data structures.
Apply important algorithmic design paradigms and methods of analysis.
Synthesize efficient algorithms in common engineering design situations.

UNIT 1: Greedy Algorithms:

Activity Selection Problem, Kruskal’s Minimum Spanning Tree Algorithm, Huffman Coding, Prim’s Minimum Spanning Tree, Dijkstra’s shortest path Algorithm, Job Sequencing Problem, Coin change Problem, K centers Problem, Minimum Number of Platforms Required for a Railway/Bus Station

UNIT 2: Dynamic Programming 1:

Overlapping Subproblems Property, Optimal Substructure Property, Longest Increasing Subsequence, Longest Common Subsequence, Edit Distance, Min Cost Path, Coin change Problem, Matrix Chain Multiplication, Binomial Coefficient, 0-1 Knapsack Problem, Egg Dropping puzzle.

UNIT 3: Dynamic Programming 2:

Longest Palindromic Subsequence, Cutting a Rod, Maximum Sum Increasing Subsequence, Longest Bitonic Subsequence, Floyd Warshall Algorithm, Palindrome Partitioning, Partition Problem, Word Wrap Problem, Box Stacking, Maximum Size square Sub-Matrix with all 1s, Ugly Numbers, Largest Sum Contiguous SubArray, Longest Palindromic Substring, Bellman-Ford Algorithm, Largest Independent Set Problem, Subset Sum, Maximum Sum Rectangle in a 2D Matrix.

UNIT 4: Pattern Searching:

Naïve Pattern Searching, KMP Algorithm, Rabin-Karp Algorithm, Boyer Moore Algorithm, Anagram Substring Search, Aho-Corasick Algorithm, Kasai’s Algorithm for Construction of LCP array from Suffix Array, Z algorithm, Manacher’s Algorithm

UNIT 5: Analysis Of Algorithms:

Comparison of time and space complexities of all sorting and searching algorithms, KMP vs Rabin-Karp vs Boyer Moore, Solving problems in Greedy vs Dynamic Programming, Quick Sort vs Merge Sort

References:

“Introduction to Algorithms” by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
“Algorithms Unlocked” by Thomas H. Cormen.

SEMESTER – VII

High End Technical & Technical Company Specific Training

Course Objectives

Course Outcomes

Upon completion of this course, the students will be able to:

Analyze the asymptotic performance of algorithms.
Write rigorous correctness proofs for algorithms.
Demonstrate familiarity with major algorithms and data structures.
Apply important algorithmic design paradigms and methods of analysis.
Synthesize efficient algorithms in common engineering design situations.

UNIT 1: Product Company Specific Training – I

UNIT 2: Product Company Specific Training – II

UNIT 3: Service Company Specific Training – I

TCS – Technical MCQ and Coding; Wipro – Automata Programming; TechMahindra, InfoView, RobertBosch, , NTT Data, Verizon, Payoda Technologies.

UNIT 4: Service Company Specific Training – II

CTS – Code Debugging & Coding Section; Accenture – Pseudo code, Network Fundamentals, Basics of Computers; MindTree – Automata Coding & Technical MCQ, MPhasis – Automata Coding; Odessa Technologies, Vuram Technologies, Hewlett Packard, HCL.

UNIT 5: Service Company Specific Training – III

Capgemini – Pseudo Code & Coding, Infosys – Pseudo Code; IBM – Coding; UGAM Solutions, Skava Systems, L&T Infotech, Bahwan Cybertech, Dhyan Infotech.

References:

“Introduction to Algorithms” by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
“Algorithms Unlocked” by Thomas H. Cormen.