data structure assignment apu

• No results found

DSTR Assignment

Share "DSTR Assignment"

Academic year: 2021

Loading.... (view fulltext now)

TECHNOLOGY PARK MALAYSIA

Ct077-3-2 dstr, data structures, uc2f1508cs / uc2f1508se / uc2f1508is, hand out date: 1 april 2016, hand in date: 30 may 2016, weightage: 60%.

INSTRUCTIONS TO CANDIDATES:

1 Submit your assignment at the administrative counter

2 Students are advised to underpin their answers with the use of references (cited using the Harvard Name System of Referencing) 3 Late submission will be awarded zero (0) unless Extenuating

Circumstances (EC) are upheld

4 Cases of plagiarism will be penalized

5 The assignment should be bound in an appropriate style (comb bound

or stapled).

6 Where the assignment should be submitted in both hardcopy and

softcopy, the softcopy of the written assignment and source code (where appropriate) should be on a CD in an envelope / CD cover and attached to the hardcopy.

LINKED DATA STRUCTURE for SPARSE MATRICES

A sparse matrix is a matrix populated primarily with zeros, and only a small number of its elements have non-zero value.

Large sparse matrices often appear in scientific and engineering applications, and being able to efficiently process such matrices can have significant impact on these applications and their usage.

In C++, a matrix of integer numbers can be defined as a two-dimensional array, like “int M [10] [10];”. However, such representation is not efficient for memory usage because it consumes a lot of memory to store very little data, since we already know the majority of values in a sparse matrix are zeros.

A better representation for a sparse matrix uses Linked Nodes data structure to store only non-zero values of the matrix.

One possibility to do that is illustrated in Fig. 2, which shows how the matrix in Fig.1 can be represented with much less memory usage. It uses “column nodes” to store matrix values, and “row nodes” to link the different rows together, and to access all “column nodes” of a particular row.

Each row or column node contains an indicator to the corresponding row-index or column-index of the matrix.

You are required to write a C++ program that implements the given sparse matrix data structure, with the following functionalities:

Fig. 1. Sparse Matrix Example of size 10 x 10

0 1 3 6 1 × 5 7 × 9 7 × 2 2 3 5 0 9 0 2 × 1 6 × 7 5 × 2 7 7 8 × Indicates row no.

Pointer to first element in the list (i.e. first non-zero element in that row)

1 3 4 5 7 9 ×

Pointer to the next non-all-zero row of the matrix Indicates non-zero value Indicates column no.

Pointer to the next non-zero element in that row

1. Suitable class(es) to represent a sparse matrix (SM) using the data structure explained

int n; int m; // # rows, # columns

… // and other necessary data members public:

SM ( int rows, int columns ); ~SM ( );

void readElements ( ); void printMatrix ( ); SM * addSM ( SM & other ); };

// and other classes, if necessary.

2. A constructor that creates an n×m matrix from given parameters: SM ( int rows, int columns ) { … }

- creates the dynamic structure, if necessary, and properly initializes it.

3. Read function to allow user to input the non-zero elements of the matrix: void readElements ( ) { … }

- reads only the non-zero elements from the user, and properly fills in the corresponding nodes, and links them correctly. User should keep inputting arbitrary [row index, column index, and value] triples, with proper indicator to stop input process.

4. Printing function to show content of a sparse matrix: void printMatrix ( ) { … }

- prints a tabular form showing all zero and non-zero elements of the matrix (something like Fig. 1)

5. Add function to sum two sparse matrices: SM * addSM ( SM & other ) { … }

- takes another sparse matrix parameter (which must have same dimensions) and returns a pointer to a newly created sparse matrix object, whose values are the sum of corresponding elements of the two matrices (“this” and “other”).

6. A destructor to free the dynamic memory allocated for a matrix: ~ SM ( ) { … }

- a suitable code that interacts with the user to test the working of all functionalities, by at least reading two matrices, printing them, and printing their sum.

Assignment Requirements

You are required to submit a hardcopy as well as a softcopy of assignment report and source code. The report should contain:

- Detailed explanation of the data structures and classes created, with proper justification on your decisions (include source code defining classes, data members, and method headers only).

- Brief explanation about the algorithms used to implement functionalities 2, 3, 4, 5, and 6 above (include code snippets of important parts of implementation).

- Source code of the main function, with screenshots showing program’s input and output interactions.

You have to present your assignment solution and answers to the lecturer during Q&A session that will be conducted after hand-in date.

If you use some code which has been taken or adapted from another source (book, magazine, internet, forum, etc.) then this must be cited and referenced using Harvard Referencing Style within your source code, and this must be mentioned explicitly in the

report. Failure to reference code properly will be treated as plagiarism.

Automated tools for checking code similarities among submissions will be used, and

all detected cases will be treated as cheating. Assessment marks are divided as follows:

Implementation Quality Documentation Presentation

Marks % 60% 10% 30%

What You Need to Hand In?

1. You are required to hand in the individual assignment report on or before the due date mentioned on the cover sheet of the assignment.

2. The attached CD should include a softcopy of the report, in addition to the C++ files of the programs. The organization of files and folders must adhere to the

following instructions precisely:

 A folder named “StudentFirstName-StudentID-Asmnt” should contain the report file (Microsoft Word), and the C++ (*.cpp / *.h) files ONLY. All additional project files (especially if you use Visual Studio) should be removed.

 Make sure to DELETE all non-source-code files, including executables (*.exe). 3. A zipped file containing CD content and named

“StudentFirstName-StudentID-Asmnt.zip” should be emailed to the lecturer at [email protected] on submission day itself. The email subject field MUST be set to: DSTR

Assignment - Full Name - StudentID. Failing to send the email on time, or not following the given guidelines will be considered as no submission.

4. You should present an executable solution during Q&A session to demonstrate program execution, the working of the data structure, your understanding of the code, and ability to modify / fix it.

5. You have to submit your assignment with Coursework Submission and Feedback Form (CSFF) attached.

Marking Criteria:

The program submitted will be evaluated according to the following performance criteria:

Distinction (90% and above)

 Program compiles and executes perfectly

 At least 90% of the required functionalities are correctly implemented

 Efficient data structures and\or algorithms are used in the implementation

 Clear coding style and structure, and code is properly commented

 Functionalities are fully tested/validated in program execution

Credit (70% – 89%)

 Program compiles and executes

 Between 70% and 90% of the required functionalities are correctly implemented

 Implementation uses a data structure or algorithm that is not most efficient

 Clear coding style, and code is properly commented

 Functionalities are not fully tested/validated in program execution

Pass (50% - 69%)

 Program compiles perfectly and executes

 Between 50% and 70% of the required functionalities are correctly implemented

 Implementation uses inefficient data structures or algorithms

 Unclear coding style, or code is not properly commented

 Functionalities are not full tested/validated in program execution, or produce errors in some cases

Marginal Fail (30% - 49%)

 Program does not compile or run, but coding logic is almost correct

 Between 30% and 50% of the required functionalities are correctly implemented

 Unclear coding style, and no comments provided

 Functionalities are not tested/validated in program execution

Fail (below 30%)

 Program is not given

 Program does not compile or run

 Less than 30% of the required functionalities are implemented

 Implementation uses very inefficient data structures or algorithms

Related documents

In the present contribution, a one-dimensional model for simulating the electric current distribution in solar cells accounting for a distributed series resistance is generalized

Gundry ,Reading Ebook The Plant Paradox: The Hidden Dangers in "Healthy" Foods That Cause Disease and Weight Gain By Steven R., M.D.. Gundry ,Reading Ebook The Plant

Facilitating joint attention with salient pointing in interactions involving children with autism spectrum disorder.. Katja Dindar, University of Eastern Finland,

Flaking may also be caused by other types of damage, such as indentations, deep seated rust, electric current damage or smearing. Fig 55 Flaked cone and rollers

Once the receiving node receives a control or data packet from the neighbouring nodes with lower depth, it will reset the void detection timer.. If no neighbouring node

In this section we introduce primitive recursive set theory with infinity (PRSω), which will be the default base theory for the rest of this thesis (occasionally exten- ded by

Dari hasil tersebut, dapat dinyatakan bahwa kinerja reduksi PAPR terbaik adalah dengan menggunakan teknik reduksi hybrid Improved PTS dan Simplified CF dengan CR yang lebh

Another feature explored was the energy envelope of the event. As the energy magnitude of an event itself differs due to the SNR and the distance between the microphone and the

Navigation Menu

Search code, repositories, users, issues, pull requests..., provide feedback.

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly.

To see all available qualifiers, see our documentation .

• Notifications

THIS REPO CONTAINS ALL THE DATA STRUCTURES LAB ASSIGNMENTS OF THE SPPU SECOND YEAR COMPUTER AND AI&DS 2019 PATTERN SYLLABUS. USE THIS FOR REFERENCE. STAR AND FORK THIS REPO.

hp1004/SPPU-SE-COMP-AI-DS-SEM-2-DSA-ALL-LAB-ASSIGNMENTS

Folders and files, repository files navigation, sppu-se-comp-ai&ds-sem-2-dsa-all-lab-assignments.

Consider a telephone book database of N clients. Make use of a hash table implementation to quickly look up client‘s telephone number. Make use of two collision handling techniques and compare them using number of comparisons required to find aset of telephone numbers (Python)

Implement all the functions of a dictionary (ADT) using hashing and handle collisions using chaining with /without replacement. Data: Set of (key, value) pairs, Keys are mapped to values, Keys must be comparable, Keys must be unique Standard Operations: Insert(key, value), Find(key), Delete(key) (python)

A book consists of chapters, chapters consist of sections and sections consist of subsections. Construct a tree and print the nodes. Find the time and space requirements of your method.

• Beginning with an empty binary search tree, Construct binary search tree by inserting the values in the order given. After constructing a binary tree -
• Insert new node.
• Find number of nodes in longest path from root.
• Minimum data value found in the tree.
• Change a tree so that the roles of the left and right pointers are swapped at every node.
• Search a value.
• Construct an expression tree from the given prefix expression eg. +-- a*bc/def and traverse it using postorder traversal(nonrecursive) and then delete the entire tree

There are flight paths between cities. If there is a flight between city A and city B then there is an edge between the cities. The cost of the edge can be the time that flight take to reach city Bfrom A, or the amount of fuel used for the journey. Represent this as a graph. The node can be represented by airport name or name of the city. Use adjacency list representation of the graph or use adjacency matrix representation of the graph. Check whether the graph is connected or not. Justify the storage representation used

You have a business with several offices; you want to lease phone lines to connect them up with each other; and the phone company charges different amounts of money to connectdifferent pairs of cities. You want a set of lines that connects all your offices with a minimum total cost. Solve the problem bysuggesting appropriate data structures.

Given sequence k = k1 <k2 < ... <kn of n sorted keys, with a search probability pi for each key ki . Build the Binary search tree that has the least search cost given the access probability for each key?

A Dictionary stores keywords & its meanings. Provide facility for adding new keywords, deleting keywords, updating valuesof any entry. Provide facility to display whole data sorted in ascending/ Descending order. Also find how many maximum comparisons may require for finding any keyword. Use Height balance tree and find the complexity for finding a keyword

• Read the marks obtained by students of second year in an online examination of particular subject. Find out maximum and minimum marks obtained in that subject. Use heap data structure.Analyze the algorithm.

Department maintains a student information. The file contains roll number, name, division and address. Allow user to add, delete information of student. Display information of particular employee. If record of student does not exist an appropriate message is displayed. If it is, then the system displays the student details. Use sequential file to maintain the data.

Company maintains employee information as employee ID, name, designation and salary. Allow user to add, deleteinformation of employee. Display information of particular employee. If employee does not exist an appropriate message is displayed. If it is, then the system displays the employee details. Use index sequential file to maintain the data.

Connect With Me:

Contributors 2.

• Python 8.8%

• Java Database Connectivity
• Spring Boot
• React Native
• Codeigniter
• Apache Tomcat
• JBoss Wildfly
• Payara Server
• Apache Web Server
• Programmer Hacks
• Solved Assignments
• Java Interview Questions
• Advance Java Interview Questions
• Android Interview Questions
• Flutter Interview Questions
• Struts Interview Questions
• Spring Boot Interview Questions
• Angular Interview Question
• React Interview Question
• Data Structures and Algorithm
• SQL Interview Question
• DevOps Interview Question
• AxonIQ Interview Questions
• Encoding & Decoding
• Encryption & Decryption
• Hash Generation
• JSON Formatter & Validator

• Rare Cod Digest

Related Articles

• Must Do Coding Questions for Companies like Amazon, Microsoft, Adobe, ...
• Practice for cracking any coding interview
• Must Do Coding Questions for Product Based Companies
• Must Do Coding Questions Company-wise
• Socket Programming in C/C++
• GET and POST requests using Python
• Top 10 Projects For Beginners To Practice HTML and CSS Skills
• Working with csv files in Python
• Types of Software Testing
• Differences between Procedural and Object Oriented Programming
• Fast I/O for Competitive Programming
• Web 1.0, Web 2.0 and Web 3.0 with their difference
• Frontend vs Backend
• Working with PDF files in Python
• 100 Days of Code - A Complete Guide For Beginners and Experienced
• XML parsing in Python
• Supervised and Unsupervised learning
• Implementing Web Scraping in Python with BeautifulSoup
• Top 10 System Design Interview Questions and Answers
• Different Ways to Connect One Computer to Another Computer
• Top Linux Distros to Consider in 2021
• OOPs | Object Oriented Design
• Data Structures and Algorithms Online Courses : Free and Paid
• Top 10 Programming Languages That Will Rule in 2021
• Genetic Algorithms
• Getting started with Machine Learning
• Top Programming Languages for Android App Development
• Socket Programming in C/C++: Handling multiple clients on server without multi threading
• Ethical Issues in Information Technology (IT)
• 7 Best Coding Challenge Websites in 2020

Table of Contents

• virtual representation of an orchestra in java
• Object Oriented Programming University Malaysia Pahang
• 5003CEM Advanced Algorithms September 2022
• CBSE4103 SOFTWARE ENGINEERING SEPTEMBER 2022
• Java Data Structure Array Assignment
• CBWP2203 WEB PROGRAMMING SEPTEMBER 2022
• CT006-3-3-APLC Resit Exam
• FIT2102 Programming Paradigms 2022
• ETW2001 2022 S2 Assessment 2
• NET3014: ADVANCED COMPUTER NETWORKS

CT087-3-3-RTS Realtime Systems

• Last Updated : 14 July, 2022

  Asia Pacific University of Technology & Innovation

This assignment has been designed for students to investigate, apply and evaluate appropriate programming methods in the planning and design of a real-time systems.

Learning Outcomes

ON COMPLETION OF THIS ASSIGNMENT YOU SHOULD BE ABLE TO DEMONSTRATE THE FOLLOWING LEARNING OUTCOME(S):  

Programme Outcomes (PO):

PLO2 – Cognitive skills

Cognitive skills relate to thinking or intellectual capabilities and the ability to apply knowledge and skills to solve problems.

PLO9 – Personal skills

Perssonal skills generally refer to the ability to engage effectively in self-directed lifelong learning and professional pathways.

Submission Requirements

Assignment Handout Date : 15 th September   2021

Assignment Due Date:  

• Proposed Simulation/Code: 8 th October 2021
• Final Code and Report: 28 th November 2021 (Week 11)

Individual Assignment – 2108CS/CS-DA

Assignment Scenario

Real-time developers have to balance 3 constraints in the quest for timely RT execution, efficiency, predictability and reliability/robustness.   For the purposes of this assignment you are required to investigate how concurrent programming techniques can used by RT systems designers to address these constraints.

Instructions

• Source two complete simulations from an online source ( Papers with Code , Github, Kaggle, BitBucket, etc) as the basis for you investigation.
• Analysis this code and provide a short commentary on the respective designs (formative assessment)
• Benchmark and profile the simulations to establish their baseline RT performance
• Refactor the simulations by applying appropriate concurrent concepts into the design of the simulation – you will be provided 2 sets of code, one per simulation.  
• Benchmark and profile your changes and compare to the original code/simulation
• Write up your findings in the form of a research paper.

Things to note:

Provide the original simulations and your brief description/outline of the respective code.

You are required to provide 2 sets of refactored code , one for each simulation.   To achieve higher marks you should undertake the refactoring incrementally.   This means planning what concurrent techniques/mechanisms you intend to utilise, apply and evaluate these changes (benchmark) incrementally and follow up with additional tweaks/changes.   This will allow to collect sufficient data to construct your research paper.  

Assignment structure:

The assignment is divided into two main tasks:

Task 1: Simulation (50%) [CLO2]

For your simulation you are required to undertake the following:

1. Design your improvements to the simulations : You are looking to redesign/refactor the simulations so as to improve performance as much as possible.

2.   Evaluate your simulations’ performance through appropriate measurement techniques/software

Task 2: Research Paper/Documentation (50%) [CLO3] – 3000 to 4000 words

The structure of the research paper is as follows (details of each section are on the next page)

• Introduction including problem statement and aim of the paper
• Background/ Literature review

Methodology

Results and discussion

Research Paper Structure:

Your Name and TP

One (1) paragraph that is a brief summary of the entire proposal, typically ranging from 150 to 250 words. It is different from a problem statement in that the abstract summarizes the entire proposal, not just mentioning the study’s purpose or hypothesis. A good abstract accurately reflects the content of the paper, while at the same time being coherent, readable, and concise.

Introduction

Introduce the reader to your paper, including a brief introduction to the general subject area and how your topic is related. Briefly point out why it is a significant topic and what contribution your work will make. .At the end of your introduction, you can add a paragraph to explain the outline of your paper. The outline is the skeleton of your document. It shows how various sections in your proposal are connected and gives the reader an indication of the logical development of your research paper.

Research Background / Literature Review

This section provides a literature review and the background for the research problem and illustrates to the reader that the researcher is knowledgeable about the scope of the theory. Research as many studies pertaining to the topic area as possible, and summarize them in a succinct manner.   The literature review should focus on programming design and its implications upon RT performance.

Your methodology should outline and discuss how you intend to carry out your investigation. It should include an overview of your chosen simulations, the changes you intend to make, and the manner in which you are planning to appraise performance.

This can include the following:

• What test(s) will you be conducting?  
• What resources will you require (testing and evaluation tools/software)?

This section is essential to most good research papers. How you study a problem is often as important as the results you collect. This section includes a description of the general means through which the goals of the study will be achieved: methods, materials, procedures, tasks, etc.

In this section you provide a detailed explanation of the results of your tests and discuss your findings.   Include screen shots, source code extracts, tables and charts to support your discussion.

Provide qualified conclusion of your research by reflecting on what you have found out and its importance to real-time development.   This section should provide a well structured discussion of the implications of your results – What are the implications of programming techniques on RT performance.  

List all publications cited in your proposal. Use the style recommended by the school or your supervisor. You should use the Harvard referencing system (see the library webpage of APU).  

Use very recent and reliable references from journal articles, conference proceedings, books, theses, etc. it is recommended to use a reference manager (such as EndNote, Mendeley, etc) to help you in formatting the references and save your time.

• Asia Pacific University of Technology & Innovation (APU)
• Assignments

Writing code in comment? Please use rarecod.com , generate link and share the link here.

• New account

Forgot your password?

Lost your password? Please enter your email address. You will receive mail with link to set new password.

Back to login