Find Jobs
Hire Freelancers

data structures (java)

$30-40 USD

En curso
Publicado hace más de 21 años

$30-40 USD

Pagado a la entrega
This is a Homework project for a Data Structures class that involves 4 parts. 1) Write the code for the public method [login to view URL](), which determines whether an undirected graph has a cycle. Base your code on either a DFS or a BFS. Test the code and determine the time and space complexities of your code. Explain. (link to the class [login to view URL] included below) 2) Let G=(V, E) be an undirected graph. A subset S of vertices of G is a dominating set iff for every vertex u in V-S, there is an edge between u and some vertex in S. A minimum dominating set is a dominating set of minimum size. The problem of finding a minimum dominating set in a graph is NP-hard. (a). [4 pts] Provide a high-level statement of a possible greedy heuristic for the minimum dominating set problem. (b) [3 pts] Give an example of a graph on which your heuristic actually produces a minimum dominating set and also one example on which it does not. (c) [8 pts] Redefine the heuristic of (a) into the public method [login to view URL](int [] dominatingSet) that returns the size of the smallest set found and put the vertices of this set into the array dominatingSet. Test your code. 3)Write a merge sort code that works on chains of elements. The output should be a sorted chain. Make your sort method a member of the class Chain or of a class that extends Chain. (link to the class [login to view URL] included below) 4)Rewrite this program using a stack to simulate the recursion. The new code should stack the boundaries of only the larger of the segments 'left' and 'right'. Show that the stack space needed is O(log(n)). /** sort a[0 : [login to view URL] - 1] using the quick sort method */ public static void quickSort(Comparable [] a) { QuickSort.a = a; if ([login to view URL] <= 1) return; //move largest element to right end [login to view URL](a, [login to view URL] - 1, [login to view URL](a, [login to view URL] -1); quickSort(0, [login to view URL] - 2); } ***Please download [login to view URL] and [login to view URL] FROM WEBSITE MENTIONEDIN DELIVERABLES ## Deliverables **Complete and fully-functional working program(s)in java in executable form as well as complete source code of all work done. **Complete ownership and distribution copyrights to all work purchased. *****Download the code for [login to view URL] and [login to view URL] from this website: Go here [login to view URL]~sahni/dsaaj/ and click on 'Programs' in the top left scroll down menu. Click on 'java codes for programs in text only' and follow directions. They are the java codes from the text. The codes are in a zip file. 1) Write the code for the public method [login to view URL](), which determines whether an undirected graph has a cycle. Base your code on either a Depth-First Search or a Breadth-First Search. Look at the methods dfs and bfs in Graph.java. Test the code and determine the time and space complexities of your code. Explain. 2) Let G=(V, E) be an undirected graph. A subset S of vertices of G is a dominating set iff for every vertex u in V-S, there is an edge between u and some vertex in S. A minimum dominating set is a dominating set of minimum size. The problem of finding a minimum dominating set in a graph is NP-hard. (a). [4 pts] Provide a high-level statement of a possible greedy heuristic for the minimum dominating set problem. (b) [3 pts] Give an example of a graph on which your heuristic actually produces a minimum dominating set and also one example on which it does not. (c) [8 pts] Redefine the heuristic of (a) into the public method [login to view URL](int [] dominatingSet) that returns the size of the smallest set found and put the vertices of this set into the array dominatingSet. Test your code. (refer to [login to view URL] for this one also) 3)Write a merge sort code that works on chains of elements. The output should be a sorted chain. Make your sort method a member of the class Chain or of a class that extends Chain. (Look at link at top of page for [login to view URL] class) 4)Rewrite this program using a stack to simulate the recursion. The new code should stack the boundaries of only the larger of the segments 'left' and 'right'. Show that the stack space needed is O(log(n)). /** sort a[0 : [login to view URL] - 1] using the quick sort method */ public static void quickSort(Comparable [] a) { QuickSort.a = a; if ([login to view URL] <= 1) return; //move largest element to right end [login to view URL](a, [login to view URL] - 1, [login to view URL](a, [login to view URL] -1); quickSort(0, [login to view URL] - 2); } ## Platform Windows 98 Java platform
ID del proyecto: 2889032

Información sobre el proyecto

2 propuestas
Proyecto remoto
Activo hace 21 años

¿Buscas ganar dinero?

Beneficios de presentar ofertas en Freelancer

Fija tu plazo y presupuesto
Cobra por tu trabajo
Describe tu propuesta
Es gratis registrarse y presentar ofertas en los trabajos
Adjudicado a:
Avatar del usuario
See private message.
$34 USD en 14 días
5,0 (14 comentarios)
3,7
3,7
2 freelancers están ofertando un promedio de $32 USD por este trabajo
Avatar del usuario
See private message.
$30,60 USD en 14 días
5,0 (18 comentarios)
4,2
4,2

Sobre este cliente

Bandera de UNITED STATES
United States
5,0
1
Miembro desde dic 3, 2002

Verificación del cliente

¡Gracias! Te hemos enviado un enlace para reclamar tu crédito gratuito.
Algo salió mal al enviar tu correo electrónico. Por favor, intenta de nuevo.
Usuarios registrados Total de empleos publicados
Freelancer ® is a registered Trademark of Freelancer Technology Pty Limited (ACN 142 189 759)
Copyright © 2024 Freelancer Technology Pty Limited (ACN 142 189 759)
Cargando visualización previa
Permiso concedido para Geolocalización.
Tu sesión de acceso ha expirado y has sido desconectado. Por favor, inica sesión nuevamente.