CSCI/CMPE 3333.02 Algorithms And Data Structures Spring 2017 - UTRGV
CSCI/CMPE 3333.02 Algorithms and Data StructuresSpring 2017Disclaimer: This syllabus is not a binding contract or a binding agreement.When necessary, changes may be made, but will announced in class, as the semester progresses,InstructorZhixiang ChenOffice: ENGR 3.293, Phone: 3520. Email: zhixiang.chen@utrgv.edu. Web: faculty .utpa. edu/zchen/ (to be updated soon)Grader: Dustin Torres, dustin.torres01@utrgv.eduA Note on BlackboardI will use Blackboard for this class. Please make sure that you assess Blackboard often for coursematerials, assignments, and especially submitting your assignments. Assignment deadlines willbe enforced by Blackboard.Homework and lab exercise grader: Ernesto Bochas Jauregui.Email: ernesto.bochasjauregui01@utrgv.eduOffice Hours:Tuesday04:30 PM -- 05:30PMWednesday10:30 AM -- 11:30 AMThursday10:30 AM -- 11:30 AMClass Schedule Lecture: MW, 12:15 PM - 01:30 PM, Engr. 1.272.All courseware, including homework assignments and lab exercises will be available atBlackBoard.Evaluations - Office of the Vice Provost for Faculty AffairsMandatory Course Evaluations period: Students are required to complete an ONLINEevaluation of this course, accessed through your UTPA account (https://my.utrgv.edu/); you willbe contacted through email with further instructions. The evaluation window closes at the middle
night of the last day of the class. Students who complete their evaluations by the day will havepriority access to their grades.Course Description (UTPA Undergraduate Catalog)This course is a continuation of data structures topics covered in CSCI/CMPE 2380. Contentincludes theoretical topics in algorithmic efficiency and complexity, along with abstract datatypes, including graphs, networks, trees, and priority queues. Search topics, including hashing,trees, external search trees (B-trees), and sorting algorithms including external sorting areintroduced and compared. Computational complexity topics include the Class P and NP, NPcompleteness and Reducibility, NP-completeness Proofs, and NP-complete Problems.Prerequisites: CSCI/CMPE 2380 and Math 3373.Text and MaterialsMark Allen Weiss, “Data Structures and Algorithm Analysis in C ,” the third edition or higher,Addison-Wesley, 2006.PrerequisitesYou are expected to have completed CSCI/CMPE 2380. CSCI/CMPE 2380 covers advancedprogramming techniques, using principles of software engineering. Files, two-dimensional arrays,stacks, queues, linear and circular linked lists, tree data structures, and some sorting andsearching method are also taught in CSCI/CMPE 2380.Course TopicsCSCI/CMPE 3333 teaches you algorithms, data structures, and software principles -- those beingfundamentals needed as essential groundwork for making the rest journey of learning computerscience. It emphasizes fundamental questions of computer science: how to organize large amountof data and how to design algorithms to process large amount data efficiently in time and space.It covers the following topics: Algorithms design and analysis: greedy algorithms, divide and conquer, dynamicprogramming, randomize algorithms, backtracking algorithms, graph algorithms, andamortized analysis, computational complexity, P vs. NP problems.Data structures: lists, stacks, queues, sets, trees, and graphs.Hashing: hashing functions, separate chaining, open addressing, rehashing, andextendible hashing.Sorting: various methods including heapsort, mergesort, quicksort, indirect sorting,bucket sorting, and external sorting.Course ObjectivesAfter completing this course, a student should be able to:
Understand basic data structures and abstract data types.Gain an appreciation of the variety, theoretical nature, and practical uses of datastructures.Select appropriate data structures for uses in computer programs.Understand the basic techniques of algorithm design and analysis.Understand the basic concepts of computational complexityDesign and implement efficient algorithms based on the selected data structures.Exam, Assignment and GradingThere will be three exams (two midterm exams and one final) for a total of 75% of the grade, 6assignments for 20% of the grade, and 5% of attendance. The letter grade will be determined asfollows:A: 90-100%B: 80-89%C: 70-79%,D: 60-69%F: 0-59%Note: Bonus projects will be announced during the semester.Assignment Policies All assignments must be in the instructor's hands before class on the due date which willbe specified on each assignment. Late assignments will be accepted up to one week witha onetime 20% late penalty.Assignments will be graded on the basis of correctness, quality of design, documentation,and style.Any assignment submitted without documentation will automatically receive a 20%deduction. Documentation, design, and style guidelines will be discussed as the semesterprogresses. No programming assignment will be graded which contains syntax errors.Student Learning OutcomesLevel 3: Synthesis and EvaluationLevel 3 outcomes are those in which the students can apply the materials in new situations. Thisis the highest level of mastery.Upon successful completion of this course, students will be able to specify data structures and operations associated with abstract data typesdefine the signature and pre- and post-conditions for operations of an abstract data typeGiven a scenario, describe the abstract data types that could be createdidentify, implement, and use the following data structures as appropriate for a givenproblem:o lists implemented as arrays or linked listso stackso queues
oo binary trees and binary search treessimple hashesimplement binary trees and binary search trees, using pre-, post-, or in-order traversals asappropriate for a given situationjudge which data model (list, tree, graph, or set) is appropriate for solving a problemjustify the choice of a data structure to solve a problem based on issues such as time,space, and of the data structure.judge which implementations are best suited for an application that requires a list datamodel: lists, circular lists, circular queues, or generalized listjudge whether an array or linked implementation is best suited or an application thatrequires a data modeljudge which graph representations (adjacency list, adjacency matrix, edge list) areappropriate for solving a problemdevelop algorithms that are based on depth- and breadth-first traversals of general trees,binary trees and graphsjudge which sort algorithms (insertion, selection, mergesort, heapsort, quicksort, radix) isappropriate for solving a problemjudge which search algorithm and data structure is appropriate for solving a problemimplement a recursive solution to a problemLevel 2: Application and AnalysisLevel 2 outcomes are those in which the students can apply the materials in familiar situations,e.g., can work a problem of familiar structure with minor changes in the details.Upon successful completion of this course, students will be able to use Big-O notation to express the best-, average-, and worst-case behaviors of analgorithmexplain the structure and use of activation recordsdetermine the best-, average- and worst-case behaviors of an algorithmassess time and space trade-offs in algorithmsexplain, code, and use quadratic and O(n log n) sorting algorithmsimplement recursive algorithms over natural numbers, lists, and treesdefine and use classes, subclasses, and inheritancedescribe the importance of encapsulation and information hidingimplement applications and simulations using data structures identified aboveimplement simple sequential and binary search algorithmsimplement a set of searching/sorting algorithmscategorize algorithms based on programming strategy, i.e., divided-and-conquer, greedy,backtracking, and dynamic programming strategiesanalyze iterative and recursive algorithms with respect to time and spacedescribe the applications for a dictionary/map ADT, e.g., the application of symbol tableGive representations for and operations on a binary tree, general tree, threaded tree, heap,binary search tree, B-tree, quadtree, and graphdetermine the order for a B-tree based on memory issues
Level 1: Knowledge and ComprehensionLevel 1 outcomes are those in which the students have been exposed to the terms and concepts ata basic level and can apply basic definitions. The materials have been presented only at asuperficial level.Upon successful completion of this course, students will be able to: recognize the standard terms associated with particular data structures, e.g., head/tail,push/popunderstand the big-O, Theta, Omega notationsunderstand the concepts of time/space complexityunderstand the basic tree conceptsunderstand the basic searching/sorting methodsrecognize the standard terms of graphsABET Student Outcomes for CSCI 3333The list of ABET student outcomes related to this class is:(a) An ability to apply knowledge of computing and mathematics appropriate to the discipline(b) An ability to analyze a problem, and identify and define the computing requirementsappropriate to its solution(c) An ability to design, implement, and evaluate a computer-based system, process, component,or program to meet desired needs(h) Recognition of the need for and an ability to engage in continuing professional development(i) An ability to use current techniques, skills, and tools necessary for computing practice.(j) An ability to apply mathematical foundations, algorithmic principles, and computer sciencetheory in the modeling and design of computer-based systems in a way that demonstratescomprehension of the tradeoffs involved in design choices.(k) An ability to apply design and development principles in the construction of software systemsof varying complexity.ABET Student Outcomes for CMPE 3333The list of ABET student outcomes related to this class is:
(a) an ability to apply knowledge of mathematics, science, and engineering(b) an ability to design and conduct experiments, as well as to analyze and interpret data(c) an ability to design a system, component, or process to meet desired needs withinrealistic constraints such as economic, environmental, social, political, ethical, health andsafety, manufacturability, and sustainability(e) an ability to identify, formulate, and solve engineering problems(i) a recognition of the need for, and an ability to engage in life-long learning(j) a knowledge of contemporary issues(k) an ability to use the techniques, skills, and modern engineering tools necessary forengineering practice.Calendar of ActivitiesInclude in this section a table or list that provides information for students regarding importantdates, assignments or activities. The UTRGV academic calendar can be found athttp://my.utrgv.edu at the bottom of the screen, prior to login. Some important dates for Spring2017 include:Nov. 1 (Tues.)Nov. 14 (Mon.)Jan. 11 (Wed.)Jan. 13 (Fri.)Jan. 16 (Mon.)Jan. 17 (Tues.)Jan. 17 – Jan. 23 (Tues. – Mon.)Jan. 30 (Mon.)Jan. 24 – Jan. 30 (Tues. – Mon.)Jan. 31 – Feb. 6 (Tues. – Mon.)Feb. 1 (Wed.)Feb. 7 – Feb. 13 (Tues. – Mon.)Mar. 13 – Mar. 18 (Mon. – Sat.)April 13 (Thurs.)April 14 – April 15 (Fri. – Sat.)May 4 (Thurs.)May 5 – 11 (Fri. – Thurs.)May 12 – 13 (Fri. – Sat.)May 15 (Mon.)Registration Begins – Graduate StudentsRegistration Begins – Undergraduate StudentsPayment DueWaitlist EndsLast day to withdraw (drop all classes) for a 100% refundMartin Luther King Jr. Holiday. No classes.Spring classes begin. Official First Class Day.Period to withdraw (drop all classes) for an 80% refundLast day to add a class or register for Spring classesPeriod to withdraw (drop all classes) for a 70% refundPeriod to withdraw (drop all classes) for a 50% refundCensus Date (Last day to drop without it appearing on the transcript)Period to withdraw (drop all classes) for a 25% refundSpring Break. No classes.Last day to drop a class (grade of DR) or withdraw (grade of W)Easter Holiday. No classes.Study Day. No classes.Final ExamsCommencement ExercisesGrades Due
UTRGV Policy StatementsSTUDENTS WITH DISABILITIES:If you have a documented disability (physical, psychological, learning, or other disability whichaffects your academic performance) and would like to receive academic accommodations, pleaseinform your instructor and contact Student Accessibility Services to schedule an appointment toinitiate services. It is recommended that you schedule an appointment with Student AccessibilityServices before classes start. However, accommodations can be provided at any time.Brownsville Campus: Student Accessibility Services is located in Cortez Hall Room 129 andcan be contacted by phone at (956) 882-7374 (Voice) or via email at ability@utrgv.edu.Edinburg Campus: Student Accessibility Services is located in 108 University Center and canbe contacted by phone at (956) 665-7005 (Voice), (956) 665-3840 (Fax), or via email atability@utrgv.edu.MANDATORY COURSE EVALUATION PERIOD:Students are required to complete an ONLINE evaluation of this course, accessed through yourUTRGV account (http://my.utrgv.edu); you will be contacted through email with furtherinstructions. Students who complete their evaluations will have priority access to their grades.ATTENDANCE:Students are expected to attend all scheduled classes and may be dropped from the course forexcessive absences. UTRGV’s attendance policy excuses students from attending class if theyare participating in officially sponsored university activities, such as athletics; for observance ofreligious holy days; or for military service. Students should contact the instructor in advance ofthe excused absence and arrange to make up missed work or examinations.SCHOLASTIC INTEGRITY:As members of a community dedicated to Honesty, Integrity and Respect, students are remindedthat those who engage in scholastic dishonesty are subject to disciplinary penalties, including thepossibility of failure in the course and expulsion from the University. Scholastic dishonestyincludes but is not limited to: cheating, plagiarism, and collusion; submission for credit of anywork or materials that are attributable in whole or in part to another person; taking anexamination for another person; any act designed to give unfair advantage to a student; or theattempt to commit such acts. Since scholastic dishonesty harms the individual, all students andthe integrity of the University, policies on scholastic dishonesty will be strictly enforced (Boardof Regents Rules and Regulations and UTRGV Academic Integrity Guidelines). All scholasticdishonesty incidents will be reported to the Dean of Students.SEXUAL HARASSMENT, DISCRIMINATION, and VIOLENCE:In accordance with UT System regulations, your instructor is a “responsible employee” forreporting purposes under Title IX regulations and so must report any instance, occurring during astudent’s time in college, of sexual assault, stalking, dating violence, domestic violence, orsexual harassment about which she/he becomes aware during this course through writing,discussion, or personal disclosure. More information can be found at www.utrgv.edu/equity,including confidential resources available on campus. The faculty and staff of UTRGV actively
strive to provide a learning, working, and living environment that promotes personal integrity,civility, and mutual respect in an environment free from sexual misconduct and discrimination.COURSE DROPS:According to UTRGV policy, students may drop any class without penalty earning a grade of DRuntil the official drop date. Following that date, students must be assigned a letter grade and can nolonger drop the class. Students considering dropping the class should be aware of the “3-peat rule”and the “6-drop” rule so they can recognize how dropped classes may affect their academic success.The 6-drop rule refers to Texas law that dictates that undergraduate students may not drop morethan six courses during their undergraduate career. Courses dropped at other Texas public highereducation institutions will count toward the six-course drop limit. The 3-peat rule refers toadditional fees charged to students who take the same class for the third time.
Email: ernesto.bochasjauregui01@utrgv.edu Office Hours: Tuesday 04:30 PM -- 05:30PM Wednesday 10:30 AM -- 11:30 AM Thursday 10:30 AM -- 11:30 AM Class Schedule Lecture: MW, 12:15 PM - 01:30 PM, Engr. 1.272. All courseware, including homework assignments and lab exercises will be available at BlackBoard.
CSCI 561 – Theory of Computation Dr. Neil T. Dantam CSCI-561, Colorado School of Mines Fall 2021 Dantam (Mines CSCI-561) Intro Fall 2021 1/32
This Software Requirements Specification details the software requirements for the FS CSCI. The FS CSCI is composed of the following Computer Software Components (CSCs): 1. Executive (0/S services, Device Drivers, Interrupt Handling, Initialization) 2. Prom Capability an.d System Initialization 3. Command Processing
CMPE 152 Compiler Design, Spring 2021, Ron Mak Page 2 of 9 Compiler construction and language design. Design and build a working compiler for a programming language that you invented. Write sample programs in your language and then compile them into executab
CMPE – 211 Preliminary Work (Pre-Lab Activity) Laboratory Experiment # 2 Textbook Material: Chapter 3 «Selections» Chapter 4 «Mathematical Functions, Characters and Strings» Chapter 5 «Loops» TASK 1 Write, Compile and Execute a Java program that prompts the user to enter a point (x, y) and checks whether the poin
3 Advanced VLSI Design CMOS Inverter CMPE 640 Propagation Delay r is equal to the resistance ratio of identically sized PMOS and NMOS transistors: R eqp/ R eqn. The optimal value of b can be found by setting When wiring cap
Principles of VLSI Design Introduction CMPE 315 Principles of VLSI Design Instructor Chintan Patel (Contact using email: cpatel2@cs.umbc.edu). Text CMOS VLSI Design: A Circuits and Systems Perspective, Third Edition. by Neil H.E. Weste and David Harris. ISBN: 0-321-14901-7, Addison Wesl
THIRD EDITION Naveed A. Sherwani Intel Corporation. KLUWER ACADEMIC PUBLISHERS NEW YORK, BOSTON, DORDRECHT, LONDON, MOSCOW. eBook ISBN: 0-306-47509-X . Graph Search Algorithms Spanning Tree Algorithms Shortest Path Algorithms Matching Algorithms Min-Cut and Max-Cut Algorithms
A. General guidance for academic writing The style of writing required for LSHTM assessments may call for different skills to those you have used in your previous education or employment. If you are not entirely confident in this, remember that the more academic writing you do, the better you will become at it. Aspects that may be new or unfamiliar, such as citing and referencing, should .
